結果
| 問題 | No.96 圏外です。 |
| ユーザー |
 Mao-beta
|
| 提出日時 | 2024-03-06 16:47:59 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,883 bytes |
| コンパイル時間 | 51 ms |
| 最終ジャッジ日時 | 2024-09-29 18:16:48 |
| 合計ジャッジ時間 | 679 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
7b4881455b5e
[/j_bin/judge_tool judge 0 30000 ../CompileMemory.txt /dev/null sud /dev/null _ pypy3 -mpy_compile Main.py]
open /home/yuki2006/gopath/src/yukicoder/judge/lang/lang.csv: no such file or directory
goroutine 1 [running]:
runtime/debug.Stack()
/usr/local/go/src/runtime/debug/stack.go:24 +0x5e
main.main.func1()
/home/yuki2006/gopath/src/yukicoder/judge/main.go:20 +0x57
panic({0x7661e0?, 0xc00006eb70?})
/usr/local/go/src/runtime/panic.go:770 +0x132
yukicoder/env.InitLangCommands(0x0)
/home/yuki2006/gopath/src/yukicoder/env/lang.go:57 +0x3a5
main.main()
/home/yuki2006/gopath/src/yukicoder/judge/main.go:42 +0x65
ソースコード
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 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
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 = ConvexHull(Vs)
d = RotatingCalipers(Vs)
ans = max(ans, d)
print(ans+2)
if __name__ == "__main__":
main()