[엘리스] 가장 가까운 두 점 찾기 (Big)

가장 가까운 두 점 찾기 (Big)

2차원 평면에 n개의 점이 있다. 이 점들 중에서 그 거리가 가장 가까운 두 점 사이의 거리의 제곱을 출력하는 프로그램을 작성하시오. 단, 두 점 (x1, y1)과 (x2, y2) 사이의 거리는 $\sqrt{(x1-x2)^2 + (y1-y2)^2}$ 로 정의된다.

예를 들어, 4개의 점이 각각 (0, 3), (1, 1), (2, 2), (7, 1) 에 위치해 있다고 하면, 가장 가까운 두 점은 (1, 1)과 (2, 2)이며, 그 거리의 제곱은 2이다.

입력

첫째 줄에 점의 개수 nn이 주어진다. (2≤n≤100,000) 두 번째 줄부터 각 점의 x좌표, y좌표가 주어진다. 각 좌표는 정수이다.

출력

가장 가까운 두 점 사이의 거리의 제곱을 출력한다.

입력 예시

4  
0 3  
1 1  
2 2  
7 1  

출력 예시

2

풀이

• 분할정복법을 이용한 풀이
  • 왼쪽에서 최솟값 계산 (재귀)
  • 오른쪽에서 최솟값 계산 (재귀)
  • 중앙을 포함한 구간에서 최솟값 계산
• 재귀식
  • 왼쪽과 오른쪽 중에서 더 작은 값을 d라고 표시
  • 중앙을 포함한 구간은 양옆으로 d만큼의 거리내에 있는 값들임 (그 이상은 무조건 d가 넘을 것이니깐)
  • 중앙점부터 거리 계산, 아래에 있는 점은 신경안쓰고 위로 d이내의 점들만 신경 (두 점의 거리기에 한쪽만 신경쓰면 모두 계산 됨, d는 위와 같은 논리)
  • 계산할 값을 리스트(considerN)에 넣고, considerN에서 원소 하나(A)를 뽑아서 뒤의 12개 정도의 원소와 비교(B, C, D ...) 
    • 위와 같이 해도 되는 이유는 considerN에 들어가는 순서가 A랑 y축으로 가장 가까운 값이기 때문에  

import sys

# 두 점간의 거리 계산 
def getDistPoints(a, b) :
    return (a[0] - b[0])**2 + (a[1] - b[1])**2

# 재귀식 
def getDistBigInternal(points, start, end) :
    if end - start <= 0 :
        return 987987987987987

    # 중앙 index
    mid = (start + end) // 2

    # 중앙의 x좌표 
    midX = (points[mid][0] + points[mid+1][0]) / 2

    # 왼쪽과 오른쪽의 최솟값 계산 
    leftDist = getDistBigInternal(points, start, mid)
    rightDist = getDistBigInternal(points, mid+1, end)
    minDistValue = min(leftDist, rightDist)


    temp = []
    tempConsider = []

    leftPtr = start
    rightPtr = mid+1

    # 중앙 index를 포함한 구간에서 최솟값 계산 
    while leftPtr <= mid or rightPtr <= end :
        leftYval = points[leftPtr][1] if leftPtr <= mid else 987987987987987
        rightYval = points[rightPtr][1] if rightPtr <= end else 987987987987987

        # 다음으로 계산할 값을 tempConsider 에 저장 
        # 다음으로 계산할 값 : Y가 더 낮은 값이면서 d라는 구간내의 값 
        if leftYval <= rightYval :
            temp.append(points[leftPtr])
            leftPtr += 1
        else :
            temp.append(points[rightPtr])
            rightPtr += 1


        # tempConsider은 결국 d구간내에 있으면서, 최초의 포인트와 위쪽으로 가까운 순서대로 계속해서 들어가게 됨 !!! 
        if temp[-1][0] >= midX - minDistValue and temp[-1][0] <= midX + minDistValue :
            tempConsider.append(temp[-1])

    for i in range(start, end+1) :
        points[i] = temp[i-start]

    considerN = len(tempConsider)

    result = 987987987987987

    # tempConsider의 값이 A를 뽑고, A랑 y간의 거리가 가까운 B가 들어가고, B를 뽑고 B랑 가까운 C를 뽑기에 최소 6개정도만 보면 가까운 값들임 (위의 그림 참고) 
    for i in range(considerN) :
        for j in range(1, 13) :
            if i + j < considerN :
                result = min(result, getDistPoints(tempConsider[i], tempConsider[i+j]))

    return min(minDistValue, result)


def getDistBig(points) :
    '''
    n개의 점이 주어질 때, 가장 가까운 두 점 사이의 거리의 제곱을 반환하는 함수를 작성하세요.

    예를 들어, 점이 4개가 있고, 각각의 좌표가 (0, 3), (1, 1), (2, 2), (7, 1) 이라면 points에는 다음과 같이 그 정보가 저장됩니다.

    points = [ (0, 3), (1, 1), (2, 2), (7, 1) ]

    이 때, 가장 가까운 두 점 사이의 거리의 제곱은 2입니다.
    '''

    pointsPrime = list(points)
    pointsPrime.sort()

    return getDistBigInternal(pointsPrime, 0, len(points)-1)

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    n = int(input())
    points = []

    for i in range(n) :
        line = [int(x) for x in input().split()]
        points.append( (line[0], line[1]) )

    print(getDistBig(points))

if __name__ == "__main__":
    main()

 

출처

• Elice