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] 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)