import sys
input = sys.stdin.readline
from math import sqrt,ceil
dx = [0,0,0,1,1,1,-1,-1,-1]
dy = [0,1,-1,0,1,-1,0,1,-1]
N = int(input())
xlist = []
ylist = []
for i in range(N):
x,y = map(int,input().split())
xlist.append((x,y))
ylist.append((y,x))
xlist.sort()
ylist.sort()
result = 10**9
for i in range(N-1):
x1,y1 = xlist[i]
x2,y2 = xlist[i+1]
result = min(result,(x1-x2)**2+(y1-y2)**2)
x1,y1 = ylist[i]
x2,y2 = ylist[i+1]
result = min(result,(x1-x2)**2+(y1-y2)**2)
if result == 0:
print(0)
else:
d = ceil(sqrt(result))
grid = {}
for i in range(N):
x,y = xlist[i]
xd,yd = x//d,y//d
if grid.get((x//d,y//d)):
grid[(x//d,y//d)].add(i)
else:
grid[(x//d,y//d)] = set([i])
for i in range(N-1):
x,y = xlist[i]
xd,yd = x//d,y//d
grid[(xd,yd)].remove(i)
for direction in range(9):
xd1,yd1 = xd+dx[direction],yd+dy[direction]
if grid.get((xd1,yd1)):
for j in grid[(xd1,yd1)]:
x1,y1 = xlist[j]
result = min(result,(x-x1)**2+(y-y1)**2)
print(result)
처음으로 푼 플래티넘 2 문제
미용실에서 머리깎으면서 혼자 생각하다가 갑자기 아이디어가 떠올랐다.
그래 격자로 나누는거야!
알고리즘은 이러하다.
1. x를 기준으로 모든 좌표를 sort한 뒤 x를 기준으로 바로 옆 좌표에 대해서 최소거리를 측정한다.
2. y를 기준으로 1번 반복
3. 최소거리가 0이면 0 출력, 아닐경우 최소거리를 올림한 값을 d 라고 둔다.
4. d를 기준으로 좌표계를 격자로 나눈다고 생각하고, grid dictionary의 (x//d,y//d) 안에 넣는다.
5. x//d,y//d를 기준으로 현위치+상하좌우+4대각선 9방향 내의 좌표에 대해서 거리를 측정한다.
6. 최솟값을 출력한다.
이렇게 할 수 있는 이유는 어차피 현 위치를 기준으로 9개의 grid안에 속해있지 않은 점이라면 무조건 사이 거리가 d를 초과하기 때문이다. 이렇게 해서 경우의 수를 줄이면 시간내에 정답을 출력할 수 있다.
python3 기준 1352ms, pypy3 기준 924ms를 기록했다.
오늘의 교훈) 플래티넘도 풀 수 있다. 쫄지말자