ABC#112 C. Pyramid

#chokudai今日の一問

3日目は，

今日の一門はPyramid！300点問題ながら参加者の多くを苦しめた一問。何度か言及してるので、解いてる人も多そうな問題かな。https://t.co/YQYRDqrt7t#chokudai今日の一問

— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 21, 2019

ABC#112 C. Pyramid

C - Pyramid

X, Y が 0から100までなので，全探索すればよさそう．

hi が全部0のときが注意，なのか? とか思ったけど，解説読むとそれはないのか．

とりあえず，hi が 0ではない組をどれか選んでおいて，そこを基準にする，という感じ．

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

static int N;
static vector<int> X;
static vector<int> Y;
static vector<long long> H;

void solve(int x0, int y0, long long h0) {
  for (int cx = 0; cx <= 100; cx++) {
    for (int cy = 0; cy <= 100; cy++) {
      long long ch = h0 + abs(x0 - cx) + abs(y0 - cy);
      bool flag = true;
      for (int i = 0; i < N; i++) {
        long long temp = ch - (abs(X[i] - cx) + abs(Y[i] - cy));
        if (temp < 0) {
          temp = 0;
        }
        if (temp != H[i]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        printf("%d %d %lld\n", cx, cy, ch);
        return;
      }
    }
  }
}

int main() {
  cin >> N;
  X.resize(N);
  Y.resize(N);
  H.resize(N);
  int x0 = 0;
  int y0 = 0;
  long long h0 = 0;
  for (int i = 0; i < N; i++) {
    int x, y;
    long long h;
    cin >> x >> y >> h;
    X[i] = x;
    Y[i] = y;
    H[i] = h;
    if (h > 0) {
      x0 = x;
      y0 = y;
      h0 = h;
    }
  }
  solve(x0, y0, h0);
  return 0;
}

https://atcoder.jp/contests/abc112/submissions/7088885