#916178 (Python3) No.96 圏外です。

• 問題: No.96 圏外です。
• ユーザー: mkawa2
• 提出日時: 2023-09-27 18:50:39
• 言語: Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1)
• 結果: AC
• 実行時間: 2,158 ms / 5,000 ms
• コード長: 3,748 bytes
• コンパイル時間: 290 ms
• コンパイル使用メモリ: 13,184 KB
• 実行使用メモリ: 75,948 KB
• 最終ジャッジ日時: 2024-07-20 13:20:05
• 合計ジャッジ時間: 23,536 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import sys
# sys.setrecursionlimit(200005)
# sys.set_int_max_str_digits(200005)
int1 = lambda x: int(x)-1
pDB = lambda *x: print(*x, end="\n", file=sys.stderr)
p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr)
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def SI(): return sys.stdin.readline().rstrip()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
# inf = -1-(-1 << 31)
inf = -1-(-1 << 63)
md = 10**9+7
# md = 998244353
class UnionFind:
    def __init__(self, n):
        self.table = [-1]*n
        self.mem = [[u] for u in range(n)]
        self.cnt = n
    def root(self, u):
        stack = []
        while self.table[u] >= 0:
            stack.append(u)
            u = self.table[u]
        for v in stack: self.table[v] = u
        return u
    def same(self, u, v):
        return self.root(u) == self.root(v)
    def merge(self, u, v):
        u = self.root(u)
        v = self.root(v)
        if u == v: return False
        su = -self.table[u]
        sv = -self.table[v]
        if su < sv: u, v = v, u
        self.table[u] = -su-sv
        self.table[v] = u
        self.mem[u] += self.mem[v]
        self.mem[v].clear()
        self.cnt -= 1
        return True
    def member(self, u):
        return self.mem[self.root(u)]
    # グループの要素数
    def size(self, u):
        return -self.table[self.root(u)]
    def allmember(self):
        return [m for m in self.mem if m]
from collections import defaultdict
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()
    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
n = II()
if n==0:
    print(1)
    exit()
ij2u = defaultdict(list)
xy = []
for u in range(n):
    x, y = LI()
    i, j = x//7, y//7
    xy.append((x, y))
    ij2u[i, j].append(u)
uf = UnionFind(n)
for i, j in ij2u:
    uu = ij2u[i, j]
    for u, v in zip(uu, uu[1:]): uf.merge(u, v)
def connect(si, sj, i, j):
    for u in ij2u[si, sj]:
        x, y = xy[u]
        for v in ij2u[i, j]:
            s, t = xy[v]
            if (x-s)**2+(y-t)**2 <= 100: return True
    return False
for si, sj in ij2u:
    for i in range(si, si+3):
        for j in range(sj-2 if i > si else sj+1, sj+3):
            if (i, j) not in ij2u: continue
            if connect(si, sj, i, j): uf.merge(ij2u[si, sj][0], ij2u[i, j][0])
ans = 0
for uu in uf.allmember():
    if len(uu) == 1: continue
    nxy = [xy[u] for u in uu]
    nxy = ConvexHull(nxy)
    ans = max(ans, RotatingCalipers(nxy))
print(ans+2)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX