[백준/BOJ] platinum2 - 2261번 가장 가까운 두 점 (Python)

▶2261 - 가장 가까운 두 점

▶문제

2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.

 

▶입력

첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다.

 

▶출력

첫째 줄에 가장 가까운 두 점의 거리의 제곱을 출력한다.

 

▶풀이

알고리즘1 수업을 듣는데 이 문제가 나왔다.
어떻게 푸나 힌트를 찾아보는데 플래티넘2 문제ㅜ 나는 아직 플래티넘4까지만 풀어봤는데ㅜ
과제도 하고 플레2 문제도 풀겸 문제를 풀어봤다.

내 실력으로 다 풀지는 못했고, 힌트를 찾아보면서 풀었다.

과제에서는 nlogn을 원해서 이 문제를 풀기 시작했는데
결과적으로 내 풀이는 n(logn)^2이 나온다
계산이 잘못 됐을수는 있지만 nlogn은 아닌거 같다

재귀를 조금 다른 방식으로 돌리거나
Line sweeping을 이용해서 풀어야할 것 같다...
아직은 실력이 많이 부족해서 조금 더 찾아보면서 공부해야겠다🥲

 

import sys


def dist(d1, d2):
    return (d1[0] - d2[0]) ** 2 + (d1[1] - d2[1]) ** 2


def divide(start, end):
    if start == end:
        return float('inf')

    if end - start == 1:
        return dist(dot[start], dot[end])

    mid = (start + end)//2
    minDist = min(divide(start, mid), divide(mid, end))

    target_dot = []
    for i in range(start, end+1):
        if (dot[mid][0] - dot[i][0]) ** 2 < minDist:
            target_dot.append(dot[i])

    target_dot.sort(key=lambda x: x[1])

    t = len(target_dot)
    for i in range(t-1):
        for j in range(i+1, t):
            if (target_dot[i][1] - target_dot[j][1]) ** 2 < minDist:
                minDist = min(minDist, dist(target_dot[i], target_dot[j]))
            else:
                break
    return minDist


n = int(sys.stdin.readline())
dot = []
for i in range(n):
    dot.append(list(map(int, sys.stdin.readline().split())))
dot.sort()
result = divide(0, n-1)
print(result)