Problem:


Score: 300 points

Problem Statement

In the Ancient Kingdom of Snuke, there was a pyramid to strengthen the authority of Takahashi, the president of AtCoder Inc.

The pyramid had center coordinates (C_X, C_Y) and height H. The altitude of coordinates (X, Y) is max(H - |X - C_X| - |Y - C_Y|, 0).  

Aoki, an explorer, conducted a survey to identify the center coordinates and height of this pyramid. As a result, he obtained the following information:  

C_X, C_Y was integers between 0 and 100 (inclusive), and H was an integer not less than 1.  

Additionally, he obtained N pieces of information. The i-th of them is: "the altitude of point (x_i, y_i) is h_i."  

This was enough to identify the center coordinates and the height of the pyramid. Find these values with the clues above.  

Constraints

N is an integer between 1 and 100 (inclusive).

x_i and y_i are integers between 0 and 100 (inclusive).

h_i is an integer between 0 and 10^9 (inclusive).

The N coordinates (x_1, y_1), (x_2, y_2), (x_3, y_3), ..., (x_N, y_N) are all different.

The center coordinates and the height of the pyramid can be uniquely identified.

Input

Input is given from Standard Input in the following format:  

N
x_1 y_1 h_1
x_2 y_2 h_2
x_3 y_3 h_3
:
x_N y_N h_N

Output

Print values C_X, C_Y and H representing the center coordinates and the height of the pyramid in one line, with spaces in between.  

Sample Input 1

4
2 3 5
2 1 5
1 2 5
3 2 5

Sample Output 1

2 2 6

In this case, the center coordinates and the height can be identified as (2, 2) and 6.  

Sample Input 2

2
0 0 100
1 1 98

Sample Output 2

0 0 100

In this case, the center coordinates and the height can be identified as (0, 0) and 100.

Note that C_X and C_Y are known to be integers between 0 and 100.

Sample Input 3

3
99 1 191
100 1 192
99 0 192

Sample Output 3

100 0 193

In this case, the center coordinates and the height can be identified as (100, 0) and 193.  



Sample input:
4
2 3 5
2 1 5
1 2 5
3 2 5


Sample output:
2 2 6

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-

def main():
    n = int(input())
    arrys = [tuple(map(int, input().split())) for _ in range(n)]
    for i in range(101):
        for j in range(101):
            for arry in arrys:
                x_tmp, y_tmp, h_tmp = arry
                if h_tmp != 0:
                    break
            H = h_tmp + abs(x_tmp - i) + abs(y_tmp - j)
            flag = 1
            for arry in arrys:
                x_t, y_t, h_t = arry
                if h_t == max(H - abs(x_t - i) - abs(y_t - j), 0):
                    flag *= 1
                else:
                    flag *= 0
            if flag == 1:
                print(i, j, H)
                exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    """
    1 <= N      <= 100
    0 <= xi, yi <= 100
    0 <= hi     <= 10^9
    """
    N = int(input())
    x, y, h = zip(*(
        map(int, input().split())
        for _ in range(N)
    ))

    import sys
    if "PyPy" in sys.version:
        ans4 = loop_xyh_N(x, y, h)
        print(*ans4)
    else:
        # ans = no_sub(x, y, h)
        ans1 = editorial_movie(x, y, h)
        ans2 = editorial_pdf(x, y, h)
        # ans3 = ref_sub_xyn(x, y, h)
        print(*ans2)
        assert ans1 == ans2 #== ans3


def h_H(cx, cy, x, y):
    return - abs(x - cx) - abs(y - cy)


def no_sub(x, y, h):
    max_h = -1
    ans = None
    dict_h = {(_x, _y): _h for _x, _y, _h in zip(x, y, h)}
    for _x, _y, _h in zip(x, y, h):
        for cx in range(1, 100+1):
            for cy in range(1, 100+1):
                tmp = h_H(cx, cy, _x, _y)
                pos = (cx, cy)
                H = _h - tmp
                if pos in dict_h and H != dict_h[pos]:
                    continue

                if H > max_h:
                    max_h = H
                    ans = _x, _y, H

                # print((_x, _y), (cx, cy), _h, tmp, sep="\t")

    return ans


def editorial_movie(x, y, h):
    """
    H >= 1, これ重要
        コンテスト中にこれを意識していなかった
        入力の制約しか意識していなかった

    h(x, y) = max(H - |x - Cx| - |y - Cy|, 0)
    より
        h(x,y) > 0:
            H            - |x - Cx| - |y - Cy| > 0
            H  = h(x, y) + |x - Cx| - |y - Cy|
        h(x,y) = 0:
            H            - |x - Cx| - |y - Cy| <= 0
            H <= h(x, y) + |x - Cx| + |y - Cy|
            頂点なら制約を満たしていない
    """
    for cx in range(100 + 1):
        for cy in range(100 + 1):
            # 頂上がどれくらいの高さであってほしいか。
            # -1はまだ良く分からない時。0以上は確定してるとき
            # -2はダメだって分かった時
            need_h = -1

            # h=0 より大きい場合の検証
            for _x, _y, _h in zip(x, y, h):
                if not _h > 0:
                    continue

                # 頂点候補座標および調査座標の組合せにおいてHになるべき値
                tmp = _h + abs(_x - cx) + abs(_y - cy)
                if need_h == -1:
                    need_h = tmp
                elif need_h != tmp:
                    need_h = -2
                    break

            if need_h == -2:
                continue

            # h=0 の検証
            for _x, _y, _h in zip(x, y, h):
                if not _h == 0:
                    continue

                # _h == 0 より、計算式上では省略してマンハッタン距離のみ求めている
                dist = abs(_x - cx) + abs(_y - cy)
                if need_h > dist:
                    need_h = -2
                    break

            if need_h == -2:
                continue

            return cx, cy, need_h


def ref_sub_xyn(x, y, h):
    """
    https://beta.atcoder.jp/contests/abc112/submissions/3348987
    """
    for cx in range(100 + 1):
        for cy in range(100 + 1):
            # 頂点候補をだしておき、0なら1に補正して確実に頂点候補とする
            # h_min, h_max は矛盾の確認用に２つ用意
            h_min = h[0] + abs(x[0] - cx) + abs(y[0] - cy)
            h_max = h_min
            if h[0] == 0:
                h_min = 1

            for _x, _y, _h in zip(x[1:], y[1:], h[1:]):
                # min: TODO
                h_max = min(h_max, _h + abs(_x - cx) + abs(_y - cy))
                if _h != 0:
                    h_min = max(h_min, _h + abs(_x - cx) + abs(_y - cy))

            if h_min == h_max:
                return cx, cy, h_min


def editorial_pdf(x, y, h):
    """
    条件を満たすピラミッドがただ 1 つなのであれば、必ず以下のものが 1 個以上存在します。
        • 調査で得られた情報のうち、hi ≥ 1 を満たす情報 (xi, yi, hi)。

    なぜなら、全部 hi = 0 であるとき、
    調査を行っていない整数座標を中心とする高さ 1 のピラミッドが条件を満たしてしまうので、
        最低でも 101×101− N 個、N = 100 の場合 10, 101 個以上の条件を満たすピラミッドが存在することになるからです。
        そこで、前述の条件を満たす情報のうち 1 個を (xt, yt, ht) とおきます。
    """
    # 候補, 調査点の高さ0のときはない（解説より）
    gx, gy, gh = (-1, -1, -1)
    for xyh in zip(x, y, h):
        if xyh[-1] >= 1:
            gx, gy, gh = xyh

    for cx in range(100 + 1):
        for cy in range(100 + 1):
            v = gh + abs(gx - cx) + abs(gy - cy)
            v = max(v, 0)
            flag = True

            for _x, _y, _h in zip(x, y, h):
                # _h との検証
                vv = v - abs(_x - cx) - abs(_y - cy)
                if _h != vv:
                    flag = False

            if flag:
                return cx, cy, v


def loop_xyh_N(x, y, h):
    h_base = max(h)

    for cx in range(100 + 1):
        for cy in range(100 + 1):
            # 探索範囲100x100より、調査点の候補より200以内
            for ch in range(h_base, h_base + 200 + 1):
                ok = True
                for _x, _y, _h in zip(x, y, h):
                    tmp = _h + abs(_x - cx) + abs(_y - cy)
                    if _h > 0 and ch != tmp:
                        ok = False
                        break
                    elif _h == 0 and ch > tmp:
                        ok = False
                        break

                if ok:
                    return cx, cy, ch


def f2(x, y, h):
    chs = []
    for _x, _y, _h in zip(x, y, h):
        for cx in range(0, 100 + 1):
            for cy in range(0, 100 + 1):
                tmp = h_H(cx, cy, _x, _y)
                print((_x, _y), (cx, cy), _h, tmp, sep="\t")

    return 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

x = []
y = []
h = []
for i in range(N):
    a,b,c = map(int, input().split())
    x.append(a)
    y.append(b)
    h.append(c)

for cx in range(101):
    for cy in range(101):
        ch = -1

        for i in range(N):
            if h[i] != 0:
                if ch == -1:
                    ch = abs(cx - x[i]) + abs(cy - y[i]) + h[i]
                else:
                    input_h = abs(cx - x[i]) + abs(cy - y[i]) + h[i]
                    if input_h != ch:
                        ch = -2
                        break
        if ch == -2:
            continue

        for i in range(N):
            if h[i] == 0:
                if ch > (abs(cx - x[i]) + abs(cy - y[i])):
                    ch = -2
        if ch != -2:
            print(cx, cy, ch)

Submission status: Accepted

Solution code:
import sys
n=int(input())

l=[list(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:-x[2])

for cx in range(101):
  for cy in range(101):
    for i in range(n):
      x,y,h=l[i]
      b=h+abs(x-cx)+abs(y-cy)
      if i==0:
        if h:
          s=set()
          s.add(b)
        else:
          s={i for i in range(b+1)}
      else:
        if not s:break
        if h:
          s&=set([b])
        else:
          s&=set(range(b+1))
    if s:
      print(cx,cy,s.pop())
      sys.exit()

Submission status: Accepted

Solution code:
N = int(input())
H = []
FIRST = []
for i in range(N):
    x,y,h = map(int,input().split())
    if h>=1 and not FIRST:
        FIRST.append([x,y,h])
    else:
        H.append([x,y,h])
        
H = FIRST + H

isok = False
for cx in range(101):
    for cy in range(101):
        notok = True
        top = -1
        for h in H:
            if top==-1:
                top = h[2] + abs(cx-h[0]) + abs(cy-h[1])
            elif h[2] != max([top-abs(h[0]-cx)-abs(h[1]-cy),0]):
                notok = False
                break
        if notok:isok = True
        if isok:break
    if isok:break
        
print(cx,cy,top)

Submission status: Accepted

Solution code:
def check():
    for k in range(0,n):
        if h[k]!=0:
            break
    for i in range(0,101):
        for j in range(0,101):
            flag=True
            h1=abs(i-x[k])+abs(j-y[k])+h[k]
            for l in range(0,n):
                if h[l]!=max(h1-abs(i-x[l])-abs(j-y[l]),0):
                    flag=False
                    break
            if flag==True:
                print(i,j,h1)
                return
            
n=int(input())
x=[0 for i in range(0,n)]
y=[0 for i in range(0,n)]
h=[0 for i in range(0,n)]
for i in range(0,n):
    x[i],y[i],h[i]=map(int,input().split())
check()

Submission status: Accepted

Solution code:
N = int(input())
data = []
for _ in range(N):
    x, y, h = list(map(int, input().split()))
    data.append([x,y,h])
for x in range(101):
    for y in range(101):
        result = 0
        for dat in data:
            if dat[2] != 0:
                result = abs(dat[0] - x) + abs(dat[1] - y) + dat[2]
                break
        flag = True
        for dat in data:
            result2 = max(result - abs(dat[0] - x) - abs(dat[1] - y) , 0)
            if result2 != dat[2]:
                flag = False
                break
        if flag == True:print(x,y,result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    xs = list()
    ys = list()
    hs = list()

    # See:
    # https://beta.atcoder.jp/contests/abc112/submissions/3360331
    # https://img.atcoder.jp/abc112/editorial.pdf
    # https://www.youtube.com/watch?v=CURWJ1Dr44A
    for i in range(n):
        xi, yi, hi = map(int, input().split())
        xs.append(xi)
        ys.append(yi)
        hs.append(hi)

        # Record a position satisfying the task conditions.
        if hi > 0:
            pos = i

    for cx in range(100 + 1):
        for cy in range(100 + 1):
            is_consistent = True
            candidate_height = abs(xs[pos] - cx) + abs(ys[pos] - cy) + hs[pos]

            for i in range(n):
                each_height = max(candidate_height - abs(xs[i] - cx) - abs(ys[i] - cy), 0)

                if hs[i] != each_height:
                    is_consistent = False
                    break

            if is_consistent:
                print(cx, cy, candidate_height)
                exit()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
x = []
y = []
h = []
for i in range(N):
    _x, _y, _h = map(int, input().split())
    x.append(_x)
    y.append(_y)
    h.append(_h)

def solve():
    for cx in range(101):
        for cy in range(101):
            H = -1
            Hmax = 1<<30
            flg = True
            for i in range(N):
                dist = abs(x[i] - cx) + abs(y[i] - cy)
                if h[i] > 0:
                    HH = h[i] + dist
                    if H < 0:
                        H = HH
                    if H != HH or H > Hmax:
                        flg = False
                        break
                else:
                    Hmax = min(Hmax, dist)
                    if H > Hmax:
                        flg = False
                        break
            if flg:
                #if Hmax == 1:
                #    H = 1
                print(cx, cy, H)
                return

solve()

Submission status: Accepted

Solution code:
N = int(input())
x = []
y = []
h = []
for i in range(N):
    _x, _y, _h = map(int, input().split())
    x.append(_x)
    y.append(_y)
    h.append(_h)

def solve():
    for cx in range(101):
        for cy in range(101):
            H = -1
            Hmax = 1<<30
            flg = True
            for i in range(N):
                dist = abs(x[i] - cx) + abs(y[i] - cy)
                if h[i] > 0:
                    HH = h[i] + dist
                    if H < 0:
                        H = HH
                    if H != HH or H > Hmax:
                        flg = False
                        break
                else:
                    Hmax = min(Hmax, dist)
                    if H > Hmax or Hmax == 0:
                        flg = False
                        break
            if flg:
                #if Hmax == 1:
                #    H = 1
                print(cx, cy, H)
                return

solve()

Submission status: Accepted

Solution code:
N = int(input())
x = []
y = []
h = []
for i in range(N):
    _x, _y, _h = map(int, input().split())
    x.append(_x)
    y.append(_y)
    h.append(_h)

def solve():
    for cx in range(101):
        for cy in range(101):
            H = -1
            Hmax = 1<<30
            flg = True
            for i in range(N):
                dist = abs(x[i] - cx) + abs(y[i] - cy)
                if h[i] > 0:
                    HH = h[i] + dist
                    if H < 0:
                        H = HH
                    if H != HH or H > Hmax:
                        flg = False
                        break
                else:
                    Hmax = min(Hmax, dist)
                    if H > Hmax or Hmax == 0:
                        flg = False
                        break
            if flg:
                if Hmax == 1:
                    H = 1
                print(cx, cy, H)
                return

solve()

Submission status: Accepted

Solution code:
n = int(input())
x = []
y = []
h = []
ans = [0,0,0]
for i in range(n):
	xyh = list(map(int, input().split()))
	x.append(xyh[0])
	y.append(xyh[1])
	h.append(xyh[2])

for i in range(101):
	for j in range(101):
		for k in range(n):
			if h[k] != 0:
				height = abs(i-x[k]) + abs(j-y[k]) + h[k]
				break
			
		flag = 0
		for k in range(n):
			if h[k] != max(height- abs(i-x[k]) - abs(j-y[k]) , 0):
				flag = 1
				break
			
		if flag == 0:
			ans = [i,j,height]
			break
		
	
print('{0} {1} {2}'.format(ans[0], ans[1], ans[2]))

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
for i in range(101):
    for j in range(101):
        H = []
        check = []
        for k in range(n):
            x = a[k][0]
            y = a[k][1]
            h = a[k][2]
            if h ==  0:
                check.append((x, y))
            else:
                H.append(h + abs(x-i) + abs(y-j))
                if len(set(H)) > 1:
                    break
            if k == n-1:
                state = False
                for s,t in check:
                    if H[0] - abs(s-i) - abs(t-j) > 0:
                        state = True
                        break
                if state:
                    break
                print(i, j, H[0])
                exit()

Submission status: Accepted

Solution code:
def ni(): 
    return int(input())
def li():
    return map(int, input().split())

xyh = [tuple(li()) for _ in range(ni())]
xmax, ymax, hmax = max(xyh, key=lambda _: _[-1])

for x_cent in range(101):
    for y_cent in range(101):
        h_cent = hmax + abs(xmax-x_cent) + abs(ymax-y_cent)
        
        for x, y, h in xyh:
            if h != max(0, h_cent - abs(x-x_cent) - abs(y-y_cent)):
                break
        else:
            print(x_cent, y_cent, h_cent)

Submission status: Accepted

Solution code:
import numpy as np

input_N = input().split()
N = int(input_N[0])

input_xyh = [input().split() for i in range(N)]

xyh = np.array(input_xyh)
xyh = xyh.astype(np.int64)
xyh = xyh.T
x = xyh[0]
y = xyh[1]
h = xyh[2]

# [0, 100]に座標があるのでMAXを定義する
coord_max = 101

for pos_y in range(coord_max):
    for pos_x in range(coord_max):
        # 頂上がどれくらいの高さであってほしいか
        # -1はまだよくわからないとき、0以上は確定
        # -2はダメ
        needH = -1

        for i in range(N):
            if h[i] > 0:
                tmp = h[i] + abs(pos_y - y[i]) + abs(pos_x - x[i])
                if needH == -1:
                    needH = tmp
                else:
                    if needH != tmp:
                        needH = -2
                        break
        if needH == -2:
            continue

        for i in range(N):
            # 高さが0の場合に矛盾してないか調べる
            if h[i] == 0:
                dist = abs(pos_y - y[i]) + abs(pos_x - x[i])
                if needH > dist:
                    needH = -2
                    break

        if needH == -2:
            continue

        # 見つけられたら答えをそのまま返す
        print(str(pos_x) + " " + str(pos_y) + " " + str(needH))

Submission status: Accepted

Solution code:
import sys
n=int(input())
X=[]
Y=[]
H=[]
MAX=100
for i in range(n):
    x,y,h=map(int,input().split())
    X.append(x)
    Y.append(y)
    H.append(h)
for posX in range(MAX+1):
    for posY in range(MAX+1):
        needH=-1
        for i in range(n):
            if H[i]>0:
                tmp=H[i]+abs(X[i]-posX)+abs(Y[i]-posY)
                if needH==-1:
                    needH=tmp
                else:
                    if needH!=tmp:
                        needH=-2
                        break
                 
        if needH==-2:
            continue
        for i in range(n):
            if H[i]==0: 
                dis=abs(X[i]-posX)+abs(Y[i]-posY)
                if needH>dis:
                    needH=-2
                    break 
        if needH==-2:
            continue
        print(posX,posY,needH)

Submission status: Accepted

Solution code:
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]

for cx in range(101):
    for cy in range(101):
        needH = -1

        for x, y, h in xyh:
            if h > 0:
                # この頂点から見て、頂上がcx, cyのときどのくらいの高さがあってほしいか
                tmp = h + abs(cx - x) + abs(cy - y)
                if needH == -1:
                    needH = tmp
                else:
                    if needH != tmp:
                        needH = -2
                        break

        if needH == -2:
            continue

        for x, y, h, in xyh:
            if h == 0:
                dist = abs(cx - x) + abs(cy - y)
                if needH - dist > 0:
                    needH = -2
                    break
        if needH == -2:
            continue

        print(cx, cy, needH)
        exit()

Submission status: Accepted

Solution code:
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]

for cx in range(101):
    for cy in range(101):
        needH = -1

        for x, y, h in xyh:
            if h > 0:
                # この頂点から見て、頂上がcx, cyのときどのくらいの高さがあってほしいか
                tmp = h + abs(cx - x) + abs(cy - y)
                if needH == -1:
                    needH = tmp
                else:
                    if needH != tmp:
                        needH = -2
                        break

        if needH == -2:
            continue

        for x, y, h, in xyh:
            if h == 0:
                dist = abs(cx - x) + abs(cy - y)
                if needH > dist:
                    needH = -2
                    break
        if needH == -2:
            continue

        print(cx, cy, needH)
        exit()

Submission status: Accepted

Solution code:
N=int(input())
xyh=[list(map(int,input().split())) for i in range(N)]
MAX=100
for PosY in range(MAX+1):
    for PosX in range(MAX+1):
        needH=-1
        for i in range(N):
             if xyh[i][2]>0:
                tmp=xyh[i][2]+abs(PosX-xyh[i][0])+abs(PosY-xyh[i][1])
                if needH==-1:
                    needH=tmp
                else:
                    if needH!=tmp:
                        needH=-2
                        break
        if needH==-2:
            continue
        for i in range(N):
            if xyh[i][2]==0:
                dist=abs(PosX-xyh[i][0])+abs(PosY-xyh[i][1])
                if needH>dist:
                    needH=-2
                    break
        if needH==-2:
            continue
        print(PosX,PosY,needH)

Submission status: Accepted

Solution code:
import numpy as np

def inpl() :
    return list(map(int,input().split()))

N = int(input())
X = np.zeros(N, dtype = int)
Y = np.zeros(N, dtype = int)
H = np.zeros(N, dtype = int)

Q = sorted([inpl() for i in range(N)], key = lambda x:x[2],reverse = True)

for j, q in enumerate(Q) :
    X[j],Y[j],H[j] = q

for cx in range(101) :
    for cy in range(101) :
        cH = H[0]+abs(X[0]-cx)+abs(Y[0]-cy)
        if np.all(H == np.maximum((cH-np.abs(X-cx)-np.abs(Y-cy)),0)) :
                  print(cx,cy,cH)

Submission status: Accepted

Solution code:
"""
C - Pyramid
"""

import numpy as np

n = int(input())

points = []
for i in range(n):
    part = list(map(int, input().split()))
    points.append(part)

#print(points)

# 100 * 100 を走査する
for cx in range(101):
    for cy in range(101):

        #print("cx", cx, "cy", cy)
        
        # -1 未定義　-2 だめ
        need_h = -1
        for point in points:

            # 地平線に隠れていない
            if point[2] > 0:
                # 高さを仮定する
                temp = point[2] + abs(cx - point[0]) + abs(cy - point[1])
                if need_h == -1:
                    need_h = temp
                else:
                    if need_h != temp:
                        need_h = -2
                        break
                
        if need_h == -2:
            continue
        
        # 通過したつまり地平線に隠れた部分
        for point in points:
            if point[2] == 0:
                dist = abs(cx - point[0]) + abs(cy - point[1])
                if need_h > dist:
                    need_h = -2
                    break
        
        if need_h == -2:
            continue
        
        print(cx, cy, need_h)
        exit()

Submission status: Accepted

Solution code:
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]

for CX in range(101):
    for CY in range(101):
        H = -1
        ans = True
        for x, y, h in xyh:
            if h > 0:
                if H == -1:
                    H = h + abs(CX - x) + abs(CY - y)
                else:
                    if H != h + abs(CX - x) + abs(CY - y):
                        ans = False
                        break
            if not ans:
                break

        for x, y, h in xyh:
            if ans and h == 0:
                if H > h + abs(CX - x) + abs(CY - y):
                    ans = False

        if ans:
            print(CX, CY, H)
            break

    if ans:
        break

Submission status: Accepted

Solution code:
def main():
    """
    1 <= N      <= 100
    0 <= xi, yi <= 100
    0 <= hi     <= 10^9
    """
    N = int(input())
    x, y, h = zip(*(
        map(int, input().split())
        for _ in range(N)
    ))

    # ans = no_sub(x, y, h)
    ans = editorial_movie(x, y, h)
    print(*ans)


def h_H(cx, cy, x, y):
    return - abs(x - cx) - abs(y - cy)


def no_sub(x, y, h):
    max_h = -1
    ans = None
    dict_h = {(_x, _y): _h for _x, _y, _h in zip(x, y, h)}
    for _x, _y, _h in zip(x, y, h):
        for cx in range(1, 100+1):
            for cy in range(1, 100+1):
                tmp = h_H(cx, cy, _x, _y)
                pos = (cx, cy)
                H = _h - tmp
                if pos in dict_h and H != dict_h[pos]:
                    continue

                if H > max_h:
                    max_h = H
                    ans = _x, _y, H

                # print((_x, _y), (cx, cy), _h, tmp, sep="\t")

    return ans


def editorial_movie(x, y, h):
    """
    H >= 1, これ重要
        コンテスト中にこれを意識していなかった
        入力の制約しか意識していなかった

    h(x, y) = max(H - |x - Cx| - |y - Cy|, 0)
    より
        h(x,y) > 0: H  = h(x, y) + |x - Cx| - |y - Cy|
        h(x,y) = 0:
            頂点なら制約を満たしていない
                    H <= h(x, y) + |x - Cx| - |y - Cy|
    """
    for cx in range(100 + 1):
        for cy in range(100 + 1):
            # 頂上がどれくらいの高さであってほしいか。
            # -1はまだ良く分からない時。0以上は確定してるとき
            # -2はダメだって分かった時
            need_h = -1

            # h=0 より大きい場合の検証
            for _x, _y, _h in zip(x, y, h):
                if not _h > 0:
                    continue

                # 頂点候補座標および調査座標の組合せにおいてHになるべき値
                tmp = _h + abs(_x - cx) + abs(_y - cy)
                if need_h == -1:
                    need_h = tmp
                elif need_h != tmp:
                    need_h = -2
                    break

            if need_h == -2:
                continue

            # h=0 の検証
            for _x, _y, _h in zip(x, y, h):
                if not _h == 0:
                    continue

                # _h == 0 より、計算式上では省略してマンハッタン距離のみ求めている
                dist = abs(_x - cx) + abs(_y - cy)
                if need_h > dist:
                    need_h = -2
                    break

            if need_h == -2:
                continue

            return cx, cy, need_h


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# encoding: utf-8
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]

ans = None
for cx in range(101):
    for cy in range(101):
        H_tmp = -1
        # print("#", cx, cy)
        for xi, yi, hi in sorted(xyh, key=lambda x: -x[2]):
            # print("##", (xi, yi, hi), H_tmp)
            dx = (xi - cx) if xi >= cx else (cx - xi)
            dy = (yi - cy) if yi >= cy else (cy - yi)
            if H_tmp == -1: H_tmp = hi + dx + dy
            elif hi == 0:
                if dx + dy < H_tmp: break
                else: continue
            elif H_tmp == hi + dx + dy: H_tmp = hi + dx + dy
            else: break
        else:
            ans = (cx, cy, H_tmp)
        if ans != None: break
    if ans != None: break

print(ans[0], ans[1], ans[2])

Submission status: Accepted

Solution code:
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]
key = False
for CX in range(101):
    for CY in range(101):
        ans = True
        H = -1
        for x, y, h in xyh:
            if h > 0:
                tmp = h + abs(x - CX) + abs(y - CY)
                if H == -1:
                    H = tmp
                else:
                    if H != tmp:
                        H = -2
                        break

        if H == -2:
            continue

        for x, y, h in xyh:
            if h == 0:
                dist = abs(x - CX) + abs(y - CY)
                if H > dist:
                    H = -2
                    break
                
        if H == -2:
            continue
        
        print(CX, CY, H)
        key = True
        break
        
    if key:
        break

Submission status: Accepted

Solution code:
N = int(input())
hxy = []
for _ in range(N):
    x, y, h = map(int, input().split())
    hxy.append((h, x, y))

# h >  0 => h == H - |x - CX| - |y - CY| (<= H)
# h == 0 => 0 >= H - |x - CX| - |y - CY|

hxy.sort(reverse=True)

MAX_X = 100
MAX_Y = 100

H = {(x, y): None for x in range(MAX_X + 1) for y in range(MAX_Y + 1)}

for h, x, y in hxy:
    for cx, cy in list(H.keys()):
        hh = h + abs(x - cx) + abs(y - cy)
        if   H[(cx, cy)] == None:
             H[(cx, cy)] =  hh
        elif H[(cx, cy)] > hh or (h > 0 and H[(cx, cy)] != hh):
             del H[(cx, cy)]

for cx, cy in H:
    print(cx, cy, H[(cx, cy)])

Submission status: Accepted

Solution code:
n = int(input())
xyh = []
for i in range(n):
    xyh.append(list(map(int,input().split())))

for i in range(n):
    if xyh[i][2] != 0:
        x1,y1,h1 = xyh[i]
        break

for cx in range(101):
    for cy in range(101):
        ch = h1 + abs(x1 - cx) + abs(y1 - cy)
        
        a = 0
        for i in range(n):
            xi, yi, hi = xyh[i]
            if hi == max(ch - abs(xi - cx) - abs(yi - cy), 0):
                a += 1
            else:
                break
        
        if a == n:
            print(cx,cy,ch)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = [LI() for _ in range(n)]
    for i in range(101):
        for j in range(101):
            rh = inf
            for x,y,h in a:
                th = h + abs(i-x) + abs(j-y)
                if rh > th:
                    rh = th
            f = True
            for x,y,h in a[1:]:
                if max(rh - abs(i-x) - abs(j-y),0) != h:
                    f = False
                    break
            if f:
                return '{} {} {}'.format(i,j,rh)

    return -1


print(main())

Submission status: Accepted

Solution code:
N=input()
A=[ map(int, raw_input().split()) for _  in range(N) ]

A.sort(key=lambda x:x[2],reverse=True)
h_highest=A[0][2]

for cx in range(101):
	for cy in range(101):
		for H in range( max(h_highest-200,0), h_highest+200):
			for x,y,h in A:
				if h==max( H-abs(x-cx)-abs(y-cy), 0):
					pass
				else:
					break
			else:
				print cx,cy,H
				quit()

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())

P = []
for i in range(N):
  P.append(list(map(int, input().split())))

P.sort(key=itemgetter(2), reverse=True)

for i in range(101):
  for j in range(101):
    H = P[0][2] + abs(i-P[0][0]) + abs(j-P[0][1])
    for k in range(1,N):
      flg = True
      if P[k][2] == max(0, H - abs(P[k][0]-i) - abs(P[k][1]-j)):
        pass
      else:
        flg = False
        break
        
    if flg:
      print(i, j, H)
      exit(0)