結果
| 問題 |
No.96 圏外です。
|
| コンテスト | |
| ユーザー |
 vwxyz
|
| 提出日時 | 2024-05-03 17:06:27 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 4,555 ms / 5,000 ms |
| コード長 | 7,002 bytes |
| コンパイル時間 | 251 ms |
| コンパイル使用メモリ | 82,396 KB |
| 実行使用メモリ | 271,316 KB |
| 最終ジャッジ日時 | 2024-11-24 20:02:16 |
| 合計ジャッジ時間 | 26,811 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 |
ソースコード
from collections import defaultdict,deque
class UnionFind:
def __init__(self,N,label=None,f=None,weighted=False,rollback=False):
self.N=N
self.parents=[None]*self.N
self.size=[1]*self.N
self.roots={i for i in range(self.N)}
self.label=label
if self.label!=None:
self.label=[x for x in label]
self.f=f
self.weighted=weighted
if self.weighted:
self.weight=[0]*self.N
self.rollback=rollback
if self.rollback:
self.operate_list=[]
self.operate_set=[]
def Find(self,x):
stack=[]
while self.parents[x]!=None:
stack.append(x)
x=self.parents[x]
if not self.rollback:
if self.weighted:
w=0
for y in stack[::-1]:
self.parents[y]=x
w+=self.weight[y]
self.weight[y]=w
else:
for y in stack[::-1]:
self.parents[y]=x
return x
def Union(self,x,y,w=None):
root_x=self.Find(x)
root_y=self.Find(y)
if self.rollback:
self.operate_list.append([])
self.operate_set.append([])
if root_x==root_y:
if self.weighted:
if self.weight[y]-self.weight[x]==w:
return True
else:
return False
else:
if self.size[root_x]<self.size[root_y]:
x,y=y,x
root_x,root_y=root_y,root_x
if self.weighted:
w=-w
if self.rollback:
self.operate_list[-1].append((self.parents,root_y,self.parents[root_y]))
self.operate_list[-1].append((self.size,root_x,self.size[root_x]))
self.operate_set[-1].append(root_y)
if self.label!=None:
self.operate_list[-1]((self.label,root_x,self.label[root_x]))
if self.weighted:
self.operate_list[-1].append((self.weight,root_y,self.weight[root_y]))
self.parents[root_y]=root_x
self.size[root_x]+=self.size[root_y]
self.roots.remove(root_y)
if self.label!=None:
self.label[root_x]=self.f(self.label[root_x],self.label[root_y])
if self.weighted:
self.weight[root_y]=w+self.weight[x]-self.weight[y]
def Size(self,x):
return self.size[self.Find(x)]
def Same(self,x,y):
return self.Find(x)==self.Find(y)
def Label(self,x):
return self.label[self.Find(x)]
def Weight(self,x,y):
root_x=self.Find(x)
root_y=self.Find(y)
if root_x!=root_y:
return None
return self.weight[y]-self.weight[x]
def Roots(self):
return list(self.roots)
def Linked_Components_Count(self):
return len(self.roots)
def Linked_Components(self):
linked_components=defaultdict(list)
for x in range(self.N):
linked_components[self.Find(x)].append(x)
return linked_components
def Rollback(self):
assert self.rollback
if self.operate_list:
for lst,x,v in self.operate_list.pop():
lst[x]=v
for x in self.operate_set.pop():
self.roots.add(x)
return True
else:
return False
def __str__(self):
linked_components=defaultdict(list)
for x in range(self.N):
linked_components[self.Find(x)].append(x)
return "\n".join(f"{r}: {linked_components[r]}" for r in sorted(list(linked_components.keys())))
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
N=int(input())
D=2001
XY=[[] for d in range(D*D)]
X,Y=[],[]
for n in range(N):
x,y=map(int,input().split())
XY[(x//10+1000)*D+(y//10+1000)].append((x,y,n))
X.append(x)
Y.append(y)
UF=UnionFind(N)
for i in range(D):
for j in range(D):
if not XY[i*D+j]:
continue
for di in range(-1,2):
for dj in range(-1,2):
if (i+di)*D+(j+dj)>=D*D or not XY[(i+di)*D+(j+dj)]:
continue
for x,y,n in XY[i*D+j]:
for xx,yy,nn in XY[(i+di)*D+(j+dj)]:
if (x-xx)**2+(y-yy)**2<=100:
UF.Union(n,nn)
ans=1
for lst in UF.Linked_Components().values():
d = RotatingCalipers(ConvexHull([(X[i],Y[i]) for i in lst]))
ans=max(ans,d+2)
print(ans)