結果
問題 | No.96 圏外です。 |
ユーザー | Mao-beta |
提出日時 | 2024-03-06 16:29:32 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,088 bytes |
コンパイル時間 | 309 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 265,784 KB |
最終ジャッジ日時 | 2024-03-06 16:29:54 |
合計ジャッジ時間 | 20,983 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 248 ms
201,144 KB |
testcase_01 | AC | 272 ms
201,144 KB |
testcase_02 | AC | 249 ms
201,144 KB |
testcase_03 | AC | 40 ms
57,824 KB |
testcase_04 | AC | 268 ms
195,488 KB |
testcase_05 | AC | 287 ms
204,796 KB |
testcase_06 | AC | 318 ms
206,460 KB |
testcase_07 | AC | 361 ms
209,916 KB |
testcase_08 | AC | 342 ms
211,836 KB |
testcase_09 | AC | 411 ms
214,936 KB |
testcase_10 | AC | 497 ms
218,700 KB |
testcase_11 | AC | 455 ms
221,960 KB |
testcase_12 | AC | 448 ms
226,004 KB |
testcase_13 | AC | 688 ms
233,000 KB |
testcase_14 | AC | 635 ms
239,756 KB |
testcase_15 | AC | 840 ms
246,268 KB |
testcase_16 | AC | 765 ms
253,344 KB |
testcase_17 | AC | 849 ms
261,388 KB |
testcase_18 | AC | 1,018 ms
264,100 KB |
testcase_19 | AC | 1,055 ms
264,612 KB |
testcase_20 | AC | 1,154 ms
260,004 KB |
testcase_21 | AC | 2,155 ms
257,684 KB |
testcase_22 | TLE | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
ソースコード
import sys import math import bisect from heapq import heapify, heappop, heappush from collections import deque, defaultdict, Counter from functools import lru_cache from itertools import accumulate, combinations, permutations, product sys.setrecursionlimit(1000000) MOD = 10 ** 9 + 7 MOD99 = 998244353 input = lambda: sys.stdin.readline().strip() NI = lambda: int(input()) NMI = lambda: map(int, input().split()) NLI = lambda: list(NMI()) SI = lambda: input() SMI = lambda: input().split() SLI = lambda: list(SMI()) EI = lambda m: [NLI() for _ in range(m)] from collections import defaultdict class UnionFind: def __init__(self, n): # 親要素のノード番号を格納 xが根のとき-(サイズ)を格納 self.par = [-1 for i in range(n)] self.n = n self.roots = set(range(n)) self.group_num = n def find(self, x): # 根ならその番号を返す if self.par[x] < 0: return x else: # 親の親は親 self.par[x] = self.find(self.par[x]) return self.par[x] def is_same(self, x, y): # 根が同じならTrue return self.find(x) == self.find(y) def unite(self, x, y): x = self.find(x) y = self.find(y) if x == y: return # 木のサイズを比較し、小さいほうから大きいほうへつなぐ if self.par[x] > self.par[y]: x, y = y, x self.group_num -= 1 self.roots.discard(y) assert self.group_num == len(self.roots) self.par[x] += self.par[y] self.par[y] = x def size(self, x): return -self.par[self.find(x)] def get_roots(self): return self.roots def group_count(self): return len(self.roots) def dist2(x1, y1, x2, y2): return (x1-x2)**2 + (y1-y2)**2 def convex(Vs): """ :param Vs(sorted by x): [[x1, y1], ... [xn, yn]] :return: upper, lower """ def cross(x1, y1, x2, y2): return x1 * y2 - y1 * x2 def is_ccw(x1, y1, x2, y2): return cross(x1, y1, x2, y2) > 0 N = len(Vs) upper = deque() upper.append(Vs[0]) upper.append(Vs[1]) for i in range(2, N): V3 = Vs[i] x3, y3 = V3 while len(upper) >= 2: V2 = upper.pop() V1 = upper.pop() x2, y2 = V2 x1, y1 = V1 upper.append(V1) if not is_ccw(x2-x1, y2-y1, x3-x2, y3-y2): upper.append(V2) upper.append(V3) break if len(upper) < 2: upper.append(V3) lower = deque() lower.append(Vs[-1]) lower.append(Vs[-2]) for i in range(N-3, -1, -1): V3 = Vs[i] x3, y3 = V3 while len(lower) >= 2: V2 = lower.pop() V1 = lower.pop() x2, y2 = V2 x1, y1 = V1 lower.append(V1) if not is_ccw(x2-x1, y2-y1, x3-x2, y3-y2): lower.append(V2) lower.append(V3) break if len(lower) < 2: lower.append(V3) return upper, lower def main(): N = NI() XY = EI(N) XY = [[x+10000, y+10000] for x, y in XY] if N == 0: print(1) return if N == 1: print(2) return # B[x][y]: Xi//10 = x, Yi//10 = y となる点のリスト B = [[[] for _ in range(2001)] for _ in range(2001)] for i, (x, y) in enumerate(XY): B[x//10][y//10].append([x, y, i]) # Bの8近傍+自身のみ通信可能か探索 DX = [0, 1, 1, 1] DY = [1, 0, 1, -1] uf = UnionFind(N) for bx in range(2001): for by in range(2001): Bxy = B[bx][by] if len(Bxy) == 0: continue # 自身 for x1, y1, i1 in Bxy: for x2, y2, i2 in Bxy: if dist2(x1, y1, x2, y2) <= 100: uf.unite(i1, i2) # 8近傍 for dx, dy in zip(DX, DY): nbx = bx + dx nby = by + dy if 0 <= nbx < 2001 and 0 <= nby < 2001: for x1, y1, i1 in Bxy: for x2, y2, i2 in B[nbx][nby]: if dist2(x1, y1, x2, y2) <= 100: uf.unite(i1, i2) # 凸包 groups = [uf.find(i) for i in range(N)] members = [[] for _ in range(N)] for i, g in enumerate(groups): members[g].append(i) ans = 0 for r, M in enumerate(members): if len(M) <= 1: continue Vs = [XY[i] for i in M] Vs.sort() upper, lower = convex(Vs) lower.pop() lower.popleft() Vs = list(upper + lower) for i in range(len(Vs)): for j in range(i+1, len(Vs)): x1, y1 = Vs[i] x2, y2 = Vs[j] d2 = dist2(x1, y1, x2, y2) ans = max(ans, d2) print(math.sqrt(ans)+2) if __name__ == "__main__": main()