ABC112 C問題

問題概要

とある場所にピラミッドが建設されていた。

ピラミッドには 中心座標 (\(C_X, C_Y\)) と 高さ \(H\)が定まっており、座標\((X, Y)\) の高度は \(max(H-|X - C_X| - |Y - C_Y|, 0)\) であった。

とある探検家の人が、このピラミッドの中心座標と高さを求めるために調査を行なった。その結果、次のような情報が得られた。

  • \(C_X, C_Y\) は 0 以上 100 以下の整数で、 \(H\) は 1 以上の整数であった。
  • 上記と別に \(N\) 個の情報が得られた。そのうち \(i\) 個目の情報は、 「座標 \((x_i, y_i)\)の高度は \(h_i\) である」

この情報は、ピラミッドの中心座標と高さを特定するのに十分であった。情報を手掛かりにこれらの値を求めよ。

制約

  • \(N\) は 1 以上 100 以下の整数
  • \(x_i, y_i\) は0 以上 100 以下の整数
  • \(h_i\) は 0 以上 109 以下の整数
  • \(N\) 個の座標 \((x_1, y_1)\), \((x_2, y_2)\), .... , \((x_N, y_N)\) はすべて異なる
  • ピラミッドの中心座標と高さをちょうど1つに特定することができる。

問題へのリンクはこちら

考えたこと

  • ピラミッドの存在する範囲が 0 ≤ X ≤ 100 かつ 0 ≤ Y ≤ 100 のそれぞれ101通り。つまり10201通りしかない。(全探索可能)
  • 全探索する際に、入力として与えられた \(x_i, y_i, h_i\) から、可能性のある頂点の高さを逆算。求めた高さに矛盾がない時に答えとなる。
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> x(n), y(n), h(n);
  for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> h[i];

  int MAXN = 100;

  for(int posY = 0; posY <= MAXN; posY++) {
    for(int posX = 0; posX <= MAXN; posX++) {
      // 頂上がどれくらいの高さであってほしいか
      // -1はまだよくわからない時、0以上は確定している時、
      // -2はダメだってわかった時
      int needH = -1;

      for(int i = 0; i < n; i++) {
        if(h[i] > 0) {
          // この頂点から見て、頂上がposY, posXの時に、
          // どのくらいの高さがあってほしいかを求める
          int tmp = h[i] + abs(posY - y[i]) + abs(posX - x[i]);
          if(needH == -1) {
            needH = tmp;
          } else {
            if(needH != tmp) {
              needH = -2;
              break;
            }
          }
        }
      }
      if(needH == -2) continue;

      for(int i = 0; i < n; i++) {
        if(h[i] == 0) {
          // 高さが0の場合に矛盾がないかどうかを調べる
          int dist = abs(posY - y[i]) + abs(posX - x[i]);
          if(needH > dist) {
            needH = -2;
            break;
          }
        }
      }
      if(needH == -2) continue;

      cout << posX << " " << posY << " " << needH << endl;
      return 0;
    }
  }

  return 0;
}