[AtCoder] ABC 112 C – Pyramid
問題
方針
中心座標の候補は最大でも \( 10000 \) 個なので、中心座標に関して全探索します。\( h_i \neq 0 \) であるとき、
\begin{eqnarray}
h_i &=& H – |x_i – C_x| – |y_i – C_y| \\
H &=& h_i + |x_i – C_x| + |y_i – C_y|
\end{eqnarray}
と高さが求まります。したがって、\( H \) がただ一つに決まるときの条件が \( N \) 個の情報と矛盾しないかを検証します。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; int x[N], y[N], h[N]; for (int i = 0; i < N; i++) { cin >> x[i] >> y[i] >> h[i]; } for (int cx = 0; cx <= 100; cx++) { for (int cy = 0; cy <= 100; cy++) { int H = 0; for (int i = 0; i < N; i++) { if (h[i] == 0) continue; ll t = abs(x[i] - cx) + abs(y[i] - cy); if (H == 0) { H = t + h[i]; } else if(H != t + h[i]){ H = 0; break; } } if (H == 0) continue; bool flag = true; for (int i = 0; i < N; i++) { if (h[i] != max(H - abs(x[i] - cx) - abs(y[i] - cy), 0)) { flag = false; break; } } if (flag) { cout << cx << " " << cy << " " << H << "\n"; return 0; } } } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません