Given n points in the plane, find the smallest distance between two of them. Brute force compares all n(n − 1)/2 pairs. Write ClosestPair, which also solves the problem by divide and conquer and counts the distance computations of both methods:
- sort the points by x (by y for equal x);
closest(low, high): with 2 or 3 points, use brute force; otherwise split at the middle, solve both halves, and let d be the smaller result;- combine: collect the points whose x is closer than d to the dividing line (the strip), sort the strip by y, and compare each point only with the following ones whose y differs by less than d.
Read n, then n lines x y. For the input
6
0 0
5 5
1 1
9 2
5 6
8 8
the program prints
Closest distance: 1.0000
Brute force: 15 distances computed
Divide and conquer: 7 distances computed
Same answer: true