BOJ 2261 가장 가까운 두 점 python

분할 정복, 스위핑 알고리즘으로 풀이가 가능한 문제인데, 스위핑은 파이썬으로 시간복잡도를 줄이기 어려워서 분할 정복을 이용하였다.

점을 x좌표 기준으로 모두 정렬하고, 중간 값을 기준으로 두 영역으로 나눈다.
하나의 영역 안에서 점 2개를 뽑는 경우와, 두 영역에서 하나씩 점을 뽑는 경우로 나눠 계산해주면 된다.

최소값을 갱신하면서 가지치기를 하는 부분이 핵심인 문제였다. 영역을 좀만 크게 잡아도 TLE를 받는다.

풀이 코드

import sys
rl = sys.stdin.readline
n = int(rl())
roc = [list(map(int, rl().split())) for _ in range(n)]
roc.sort()
 
def cal(a, a0):
    return (a[0]-a0[0])**2+(a[1]-a0[1])**2
 
def divCon(dots, dotNum):
    if dotNum == 2: return cal(dots[0], dots[1])
    elif dotNum == 3: return min(cal(dots[0], dots[1]),cal(dots[1], dots[2]),cal(dots[0], dots[2]))
 
    midx = (dots[dotNum//2][0]+dots[dotNum//2-1][0])//2
    mind = min(divCon(dots[:dotNum//2], dotNum//2), divCon(dots[dotNum//2:], (dotNum+1)//2))
 
    checkdot = []
    for x, y in dots:
        if (midx-x)**2>=mind:
            if x>midx: break
            continue
        checkdot.append([x,y])
    checkdot.sort(key = lambda x: x[1])
 
    for i in range(len(checkdot)-1):
        for j in range(i+1, len(checkdot)):
            if (checkdot[i][1]-checkdot[j][1])**2>=mind: break
            mind = min(mind, cal(checkdot[i], checkdot[j]))
    return mind
 
print(divCon(roc, n))