Find the two points that are nearest to each other, without trying every pair.
What to build
A divide-and-conquer program that finds the squared distance between the closest two points.
Requirements
- Sort the points by x first.
- Solve small ranges of up to 3 points directly.
- Combine by checking the strip of points near the dividing line, sorted by y.
- Print the squared distance, so that no decimals are needed.
Input
The first line has n. Each of the next n lines has a point x y.
Output
The smallest squared distance between two points.
Constraints
2 ≤ n ≤ 300, and |x|, |y| ≤ 10000. Two points may be the same.
Example
Input:
6
2 3
12 30
40 50
5 1
12 10
3 4
Output:
2
Why it works
Two points in the strip that are less than best apart must be close in y too, and a geometric argument limits how many can be that close. So the combine step is fast, and the whole method is O(n log² n) with this simple strip sort.
Examples
6 2 3 12 30 40 50 5 1 12 10 3 4
2
2 0 0 3 4
25
Hints
Hint 1
Sort the points by x, split them in half, and solve each half. Let `best` be the smaller answer.
Hint 2
A closer pair can only cross the middle if both points lie within `best` of the dividing line in x, so collect those points.
Hint 3
Sort that strip by y. Each point only needs comparing with the next few, stopping once the y gap is too large.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
typedef struct {
int x, y;
} Point;
Point p[300], strip[300];
int dist2(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int closest(int lo, int hi) {
int best = 2000000000;
if (hi - lo < 3) {
for (int i = lo; i <= hi; i++)
for (int j = i + 1; j <= hi; j++)
if (dist2(p[i], p[j]) < best) best = dist2(p[i], p[j]);
return best;
}
int mid = (lo + hi) / 2;
int midx = p[mid].x;
int left = closest(lo, mid);
int right = closest(mid + 1, hi);
best = left < right ? left : right;
int k = 0;
for (int i = lo; i <= hi; i++)
if ((p[i].x - midx) * (p[i].x - midx) < best) strip[k++] = p[i];
for (int i = 1; i < k; i++) {
Point key = strip[i];
int j = i - 1;
while (j >= 0 && strip[j].y > key.y) {
strip[j + 1] = strip[j];
j--;
}
strip[j + 1] = key;
}
for (int i = 0; i < k; i++) {
for (int j = i + 1; j < k && (strip[j].y - strip[i].y) * (strip[j].y - strip[i].y) < best; j++)
if (dist2(strip[i], strip[j]) < best) best = dist2(strip[i], strip[j]);
}
return best;
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d %d", &p[i].x, &p[i].y);
for (int i = 1; i < n; i++) {
Point key = p[i];
int j = i - 1;
while (j >= 0 && p[j].x > key.x) {
p[j + 1] = p[j];
j--;
}
p[j + 1] = key;
}
printf("%d\n", closest(0, n - 1));
return 0;
}