이 문제에서는 2D 평면에 n개의 점 집합이 제공됩니다. 이 문제에서는 거리가 최소인 점 쌍을 찾아야 합니다.
이 문제를 해결하려면 두 점 사이의 가장 작은 거리를 재귀적으로 계산한 후 점을 두 개의 반으로 나누어야 합니다. 중간 선으로부터의 거리를 사용하여 점을 일부 스트립으로 분리합니다. 스트립 배열에서 가장 작은 거리를 찾습니다. 처음에는 데이터 포인트로 두 개의 목록이 생성되며, 하나의 목록은 x 값으로 정렬된 포인트를 보유하고 다른 목록은 y 값으로 정렬된 데이터 포인트를 보유합니다.
이 알고리즘의 시간 복잡도는 O(n log n)입니다.
입력 및 출력
Input: A set of different points are given. (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4) Output: Find the minimum distance from each pair of given points. Here the minimum distance is: 1.41421 unit
알고리즘
findMinDist(pointsList, n)
입력: 주어진 포인트 목록과 목록의 포인트 수.
출력 - 두 점에서 최소 거리를 찾습니다.
Begin min := ∞ for all items i in the pointsList, do for j := i+1 to n-1, do if distance between pointList[i] and pointList[j] < min, then min = distance of pointList[i] and pointList[j] done done return min End
stripClose(스트립, 크기, 거리)
입력 - 스트립의 다른 점, 점의 수, 정중선으로부터의 거리.
출력 - 스트립의 두 점에서 가장 가까운 거리입니다.
Begin for all items i in the strip, do for j := i+1 to size-1 and (y difference of ithand jth points) <min, do if distance between strip[i] and strip [j] < min, then min = distance of strip [i] and strip [j] done done return min End
findClosest(xSorted, ySorted, n)
입력 - x 값으로 정렬된 포인트 및 y 값으로 정렬된 포인트, 포인트 수.
출력 - 총 점 집합에서 최소 거리를 찾습니다.
Begin if n <= 3, then call findMinDist(xSorted, n) return the result mid := n/2 midpoint := xSorted[mid] define two sub lists of points to separate points along vertical line. the sub lists are, ySortedLeft and ySortedRight leftDist := findClosest(xSorted, ySortedLeft, mid) //find left distance rightDist := findClosest(xSorted, ySortedRight, n - mid) //find right distance dist := minimum of leftDist and rightDist make strip of points j := 0 for i := 0 to n-1, do if difference of ySorted[i].x and midPoint.x<dist, then strip[j] := ySorted[i] j := j+1 done close := stripClose(strip, j, dist) return minimum of close and dist End
예시
#include <iostream> #include<cmath> #include<algorithm> using namespace std; struct point { int x, y; }; intcmpX(point p1, point p2) { //to sort according to x value return (p1.x < p2.x); } intcmpY(point p1, point p2) { //to sort according to y value return (p1.y < p2.y); } float dist(point p1, point p2) { //find distance between p1 and p2 return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y)); } float findMinDist(point pts[], int n) { //find minimum distance between two points in a set float min = 9999; for (int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) if (dist(pts[i], pts[j]) < min) min = dist(pts[i], pts[j]); return min; } float min(float a, float b) { return (a < b)? a : b; } float stripClose(point strip[], int size, float d) { //find closest distance of two points in a strip float min = d; for (int i = 0; i < size; ++i) for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) if (dist(strip[i],strip[j]) < min) min = dist(strip[i], strip[j]); return min; } float findClosest(point xSorted[], point ySorted[], int n){ if (n <= 3) return findMinDist(xSorted, n); int mid = n/2; point midPoint = xSorted[mid]; point ySortedLeft[mid+1]; // y sorted points in the left side point ySortedRight[n-mid-1]; // y sorted points in the right side intleftIndex = 0, rightIndex = 0; for (int i = 0; i < n; i++) { //separate y sorted points to left and right if (ySorted[i].x <= midPoint.x) ySortedLeft[leftIndex++] = ySorted[i]; else ySortedRight[rightIndex++] = ySorted[i]; } float leftDist = findClosest(xSorted, ySortedLeft, mid); float rightDist = findClosest(ySorted + mid, ySortedRight, n-mid); float dist = min(leftDist, rightDist); point strip[n]; //hold points closer to the vertical line int j = 0; for (int i = 0; i < n; i++) if (abs(ySorted[i].x - midPoint.x) <dist) { strip[j] = ySorted[i]; j++; } return min(dist, stripClose(strip, j, dist)); //find minimum using dist and closest pair in strip } float closestPair(point pts[], int n) { //find distance of closest pair in a set of points point xSorted[n]; point ySorted[n]; for (int i = 0; i < n; i++) { xSorted[i] = pts[i]; ySorted[i] = pts[i]; } sort(xSorted, xSorted+n, cmpX); sort(ySorted, ySorted+n, cmpY); return findClosest(xSorted, ySorted, n); } int main() { point P[] ={{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}; int n = 6; cout<< "The minimum distance is " <<closestPair(P, n); }
출력
The minimum distance is 1.41421