Baekjoon 2261

09 Feb 2024 in Study / Computer science on Baekjoon 2261

Devide & Conquer

Baekjoon 2261

Description

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

Input

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

Output

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

Example I & O

Input
4
0 0
10 10
0 10
10 0

Output
100

My solution

import sys
input = sys.stdin.readline
print = sys.stdout.write
def calDistance(start, end):                               
    minDistance = ((data[start][0] - data[start + 1][0]) ** 2 + (data[start][1] - data[start + 1][1]) ** 2)
    for i in range(start, end):
        for j in range(i + 1, end + 1):
            d = ((data[i][0] - data[j][0]) ** 2 + (data[i][1] - data[j][1]) ** 2)
            if minDistance > d:
                minDistance = d


    return minDistance


def func(start, end):
    if end - start <= 2:
        minDistance = calDistance(start, end)
        return minDistance

    mid = (start + end) // 2
    midLine_x = data[mid][0]


    left_min = func(start, mid)
    minDistance = left_min
    right_min = func(mid + 1, end)

    if left_min <= right_min:
        minDistance = left_min
    else:
        minDistance = right_min

    newCoordinateList = []
    for i in range(start, end + 1):
        if midLine_x - (minDistance) ** 0.5 <= data[i][0] <= midLine_x + (minDistance) ** 0.5:
            newCoordinateList.append(data[i])
    newCoordinateList.sort(key=lambda x : x[1])

    for i in range(len(newCoordinateList) - 1):
        for j in range(i + 1, len(newCoordinateList)):
            if (newCoordinateList[j][1] - newCoordinateList[i][1]) ** 2 >= minDistance:
                break
            currentDistance = (newCoordinateList[j][0] - newCoordinateList[i][0]) ** 2 + (newCoordinateList[j][1] - newCoordinateList[i][1]) ** 2
            if currentDistance < minDistance:
                minDistance = currentDistance

    return minDistance   

N = int(input())

data = []

for i in range(N):
    x, y = map(int, input().split())
    data.append([x, y])

data.sort(key=lambda x : x[0])

print(str(func(0, len(data) - 1)))   

• Sketch

Use Devide & Conquer
1^st : sorting all of points (standard : x coordinate)
2^nd : devide to two sections
3^rd : Calculate minimum distance in left section and right section
4^th : left_min VS right_min : Winner is min_d
However, We should also consider the distance between one point from left section and another point from right section
5^th : We extract the points from both sections whose x coordinates are involved in the range middle_line - min_d <= x <= middle_line + min_d + We calculate all distance between extracted points, ignoring the specific combination of two points whose y difference >= min_d

• Code Analysis
  

def calDistance(start, end):                               
    minDistance = ((data[start][0] - data[start + 1][0]) ** 2 + (data[start][1] - data[start + 1][1]) ** 2)
    for i in range(start, end):
        for j in range(i + 1, end + 1):
            d = ((data[i][0] - data[j][0]) ** 2 + (data[i][1] - data[j][1]) ** 2)
            if minDistance > d:
                minDistance = d


    return minDistance

CalDistance : calculate minimum distance in section that the number of elements is 2 or 3

---

def func(start, end):
    if end - start <= 2:
        minDistance = calDistance(start, end)
        return minDistance

    mid = (start + end) // 2
    midLine_x = data[mid][0]


    left_min = func(start, mid)
    minDistance = left_min
    right_min = func(mid + 1, end)

    if left_min <= right_min:
        minDistance = left_min
    else:
        minDistance = right_min

1^st ~ 4^th
Repeating division until the section has 2 or 3 elements by using recursion
Calculate left_min and right_min
Select minDistance from left_min and right_min

---

newCoordinateList = []
for i in range(start, end + 1):
    if midLine_x - (minDistance) ** 0.5 <= data[i][0] <= midLine_x + (minDistance) ** 0.5:
        newCoordinateList.append(data[i])
newCoordinateList.sort(key=lambda x : x[1])

for i in range(len(newCoordinateList) - 1):
    for j in range(i + 1, len(newCoordinateList)):
        if (newCoordinateList[j][1] - newCoordinateList[i][1]) ** 2 >= minDistance:
            break
        currentDistance = (newCoordinateList[j][0] - newCoordinateList[i][0]) ** 2 + (newCoordinateList[j][1] - newCoordinateList[i][1]) ** 2
        if currentDistance < minDistance:
            minDistance = currentDistance

return minDistance

5^th
Extract the points whose x coordinate satisfies the x conditions (midLine_x - minDistance <= x <= midLine_x + minDistance)
Calculate all distance from newCoordinateList but it should ignore the case that y difference >= minDistance
Update minDistance

---