백준 2261 - 가장 가까운 두 점 (파이썬)

Answer

import sys

n = int(sys.stdin.readline())
c = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
c.sort()

def getDist(x1, x2):
    return (x1[0] - x2[0]) ** 2 + (x1[1] - x2[1]) ** 2

def solution(s, e):
    if s == e:
        return float('inf')

    if e - s == 1:
        return getDist(c[s], c[e])

    m = (s + e) // 2
    md = min(solution(s, m), solution(m, e))

    tmp = []
    for i in range(s, e + 1):
        if (c[m][0] - c[i][0]) ** 2 < md:
            tmp.append(c[i])

    tmp.sort(key = lambda x : x[1])
    t = len(tmp)

    for i in range(t - 1):
        for j in range(i + 1, t):
            if (tmp[i][1] - tmp[j][1]) ** 2 < md:
                md = min(getDist(tmp[i], tmp[j]), md)
            else:
                break

    return md

print(solution(0, n - 1))