#418048 (PyPy3) No.96 圏外です。

• 問題: No.96 圏外です。
• ユーザー: mkawa2
• 提出日時: 2020-01-17 01:12:56
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,056 ms / 5,000 ms
• コード長: 3,643 bytes
• コンパイル時間: 291 ms
• コンパイル使用メモリ: 82,464 KB
• 実行使用メモリ: 137,880 KB
• 最終ジャッジ日時: 2024-06-24 19:38:31
• 合計ジャッジ時間: 13,772 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
other	AC * 28

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
    def root(self, u):
        pu = self.state[u]
        if pu < 0: return u
        res = self.state[u] = self.root(pu)
        return res
    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        state = self.state
        if ru == rv: return
        if state[ru] > state[rv]: ru, rv = rv, ru
        if state[ru] == state[rv]: state[ru] -= 1
        state[rv] = ru
def ConvexHull(xy):
    def NG(x, y):
        x0, y0 = res[-2]
        x1, y1 = res[-1]
        return (x - x0) * (y1 - y0) - (x1 - x0) * (y - y0) >= 0
    res = []
    xy.sort(key=lambda p: (p[0], p[1]))
    for x, y in xy:
        while len(res) > 1 and NG(x, y): res.pop()
        res.append((x, y))
    under_n = len(res)
    for x, y in xy[-2::-1]:
        while len(res) > under_n and NG(x, y): res.pop()
        res.append((x, y))
    return res[:-1]
def RotatingCalipers(xy):
    def dist(i, j):
        ix, iy = xy[i]
        jx, jy = xy[j]
        return (ix - jx) ** 2 + (iy - jy) ** 2
    def vec(i):
        x0, y0 = xy[i]
        x1, y1 = xy[(i + 1) % n]
        return x1 - x0, y1 - y0
    def outer(i, j):
        vix, viy = vec(i)
        vjx, vjy = vec(j)
        return vix * vjy - viy * vjx
    n = len(xy)
    if n < 2: return 0
    if n == 2: return dist(0, 1) ** 0.5
    res = 0
    i = xy.index(min(xy))
    j = xy.index(max(xy))
    si, sj = i, j
    while i != sj or j != si:
        res = max(res, dist(i, j))
        if outer(i, j) > 0:
            j = (j + 1) % n
        else:
            i = (i + 1) % n
    return res ** 0.5
def main():
    n = II()
    # 例外処理
    if n == 0:
        print(1)
        exit()
    # 負の座標が面倒なので10000を足して正にする
    # 座標平面を一辺10の正方形ゾーンに分割して、座標をゾーンごとに振り分ける
    zone = {}
    xy = []
    for i in range(n):
        x, y = MI()
        x, y = x + 10000, y + 10000
        xy.append((x, y))
        x, y = x // 10, y // 10
        zone.setdefault((x, y), [])
        zone[x, y].append(i)
    # print(zone)
    # 自分自身も含めて隣接9ゾーンで10km以内の座標同士を結合していく
    # 実際は未訪の5ゾーン（自分と上と右3つ）を調べればよい
    uf = UnionFind(n)
    for (zx, zy), ii in sorted(zone.items(), key=lambda k: (k[0], k[1])):
        for i in ii:
            ix, iy = xy[i]
            for nzx, nzy in [(zx, zy), (zx, zy + 1), (zx + 1, zy - 1), (zx + 1, zy), (zx + 1, zy + 1)]:
                if (nzx, nzy) not in zone: continue
                for j in zone[nzx, nzy]:
                    if i == j: continue
                    jx, jy = xy[j]
                    if (ix - jx) ** 2 + (iy - jy) ** 2 <= 100: uf.merge(i, j)
    # 結合成分どうしでグループ分け
    rtoxy = defaultdict(list)
    for i in range(n):
        rtoxy[uf.root(i)].append(xy[i])
    # print(rtoxy)
    # グループごとに最遠点を計算
    ans = 2
    for v in rtoxy.values():
        if len(v) == 1: continue
        # 凸包を作る
        cnv = ConvexHull(v)
        # 最大距離を求める
        ans = max(ans, RotatingCalipers(cnv) + 2)
    print(ans)
main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX