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; }