[BOJ] 2261 가장 가까운 두 점

https://www.acmicpc.net/problem/2261

Sweep 알고리즘 풀다가 여기까지 도달했다. 그런데 1차원 직선 상에 놓인 점 중에 가까운 것은 구할 수 있겠는데 2차원에서는 어떻게 접근해야할 지 감을 잡지 못했다.

https://www.acmicpc.net/blog/view/25
참고해서 풀었다.

점을 x로 정렬해서 candidate라는 집합에 앞의 두 점을 넣고, 두 점 사이의 거리를 먼저 측정한다.
그러고 나서 점을 돌면서 최초에 측정한 거리보다 크다면 넘기고, 작다면 y거리까지 측정해서 최소거리를 업데이트 하는 방식이다.

n = int(input())

dots = [tuple(map(int, input().split())) for _ in range(n)]

dots.sort()

def getDist(a, b):
  return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

candidate = {dots[0], dots[1]}

answer = getDist(dots[0], dots[1])

start = 0
for i in range(2, n):
  now = dots[i]
  while start < i:
    p = dots[start]
    dx = now[0] - p[0]
    if dx * dx > answer:
      candidate.discard(p)
      start += 1
    else:
      break
  
  d = answer ** 0.5 + 1
  lower_y = now[1] - d
  upper_y = now[1] + d
  for c in candidate:
    if lower_y <= c[1] <= upper_y:
      answer = min(answer, getDist(now, c))
  
  candidate.add(now)
  
print(answer)

c++코드를 python 코드로 옮겨서 바꿨다.
candidate안에는 0, 1번 점을 넣고 answer는 0, 1번 점 사이의 거리로 업데이트 했다.

2번 점부터 for문을 시작했는데, 왼쪽에 있는 점들과 비교해서 x거리가 answer보다 작다면 멈추고, y거리를 비교해서 answer를 업데이트 해줬다.

그런데 파이썬 코드라서 그런지 아니면 코드 해석을 잘못한건지 시간초과가 발생한다.
시간을 두고 연구해봐야겠다.