[ Divide and Conquer ] Closest Pair
·
CS/Algorithm
Closest pair Computational Geometry직관과 심하게 충돌하는 경우 많음주어진 점들 중에서 가장 가까우 쌍을 찾기(2차원)Usually Input is given by Coordinates좌표 형태로 입력이 들어온다. (a,b), (c,d)가 주어진다면 -> \(\sqrt{(a-c)^2 + (b-d)^2}\) 을 모든 쌍에 대해서 하면 \(n^2\)개가 생기고 이 중에 제일 작은거 찾으면 됨sqrt()라는 함수로 루트를 계산할 수 있지만, 무리수이기 때문에 정확한 계산이 불가능하다. 1 - Dimensional Versionsorting 후, 가장 옆에것과의 거리를 비교하여 가장 짧은 것을 고르면 됨Divide and ConquerFirst, Sort by x coordinate..