結果

問題 No.960 マンハッタン距離3
ユーザー lam6er
提出日時 2025-04-09 21:02:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,314 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 83,036 KB
実行使用メモリ 77,144 KB
最終ジャッジ日時 2025-04-09 21:04:15
合計ジャッジ時間 17,146 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 75 WA * 33 TLE * 1 -- * 107
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    W = int(data[0])
    H = int(data[1])
    N = int(data[2])
    
    points = []
    s_list = []
    d_list = []
    for i in range(N):
        x = int(data[3 + 2 * i])
        y = int(data[4 + 2 * i])
        points.append((x, y))
        s = x + y
        d = x - y
        s_list.append(s)
        d_list.append(d)
    
    max_s = max(s_list)
    min_s = min(s_list)
    max_d = max(d_list)
    min_d = min(d_list)
    
    S = max_s - min_s
    D = max_d - min_d
    
    candidates = []
    if S == D:
        A = (max_s + min_s) // 2
        B = (max_d + min_d) // 2
        if (max_s + min_s) % 2 == 0 and (max_d + min_d) % 2 == 0:
            X = (A + B) // 2
            Y = (A - B) // 2
            if 1 <= X <= W and 1 <= Y <= H:
                candidates.append((X, Y))
    
    found = False
    valid = []
    for X in range(max(1, min(p[0] for p in points) - 3), min(W, max(p[0] for p in points) + 3) + 1):
        for Y in range(max(1, min(p[1] for p in points) - 3), min(H, max(p[1] for p in points) + 3) + 1):
            distances = set()
            for x, y in points:
                dist = abs(X - x) + abs(Y - y)
                distances.add(dist)
                if len(distances) > 1:
                    break
            if len(distances) == 1:
                valid.append((X, Y))
                found = True
    
    if found:
        valid = list(set(valid))
        count = 0
        for X, Y in valid:
            d = abs(X - points[0][0]) + abs(Y - points[0][1])
            valid_dist = True
            for x, y in points:
                if abs(X - x) + abs(Y - y) != d:
                    valid_dist = False
                    break
            if valid_dist:
                count += 1
        print(count)
        return
    
    if candidates:
        X, Y = candidates[0]
        d = abs(X - points[0][0]) + abs(Y - points[0][1])
        valid_candidate = True
        for x, y in points:
            if abs(X - x) + abs(Y - y) != d:
                valid_candidate = False
                break
        if valid_candidate and 1 <= X <= W and 1 <= Y <= H:
            print(1)
        else:
            print(0)
    else:
        print(0)

if __name__ == '__main__':
    main()
0