AtCoder Beginner Contest 112 C - Pyramid

beta.atcoder.jp

問題概要

（以下、座標は全部整数とする）
ピラミッドがある。
(Cx,Cy)が一番高く、ある(x,y)での高さは|Cx-x|+|Cy-y|だけ低い。高さは負にならない。
N個の座標とそこの高さが与えられるので、中心の座標と高さを求めたい。

解法

N=100, Cx,Cy<=100より全探索できる。
中心座標の候補xとyは0から100まで、高さの候補hは入力で一番高かったものmからm+100まで、入力が条件に合うかどうか見ていく。1つでも合わなかったらその時点で打ち切り。N個全部大丈夫だったら出力して終了。
x,yは0以上100以下だけど高さは10**9までなことに注意。（本番では8WAもしてしまった。気をつけよう！）

N = int(input())
L = [list(map(int, input().split())) for k in range(N)]
m = 0
for l in L:
    m = max(m,l[2])

for x in range(101):
    for y in range(101):
        for h in range(m,m+101):
            f = 1
            for l in L:
                if l[2]!=max(h-abs(l[0]-x)-abs(l[1]-y),0):
                    f = 0
                    break
            if f:
                print(x,y,h)
                exit(0)