001package algs91; // section 9.8
002import stdlib.*;
003import java.util.Arrays;
004import algs12.Point2D;
005import algs22.Merge;
006/* ***********************************************************************
007 *  Compilation:  javac ClosestPair.java
008 *  Execution:    java ClosestPair < input.txt
009 *  Dependencies: Point2D.java
010 *
011 *  Given N points in the plane, find the closest pair in N log N time.
012 *
013 *  Note: could speed it up by comparing square of Euclidean distances
014 *  instead of Euclidean distances.
015 *
016 *  % java ClosestPair < rs1423.txt
017 *  15.0 from (11364.0, 12693.0) to (11373.0, 12705.0)
018 *
019 *************************************************************************/
020
021
022public class ClosestPair {
023        // closest pair of points and their Euclidean distance
024        private Point2D best1, best2;
025        private double bestDistance = Double.POSITIVE_INFINITY;
026
027        public ClosestPair(Point2D[] points) {
028                int N = points.length;
029                if (N <= 1) return;
030
031                // sort by x-coordinate (breaking ties by y-coordinate)
032                Point2D[] pointsByX = new Point2D[N];
033                for (int i = 0; i < N; i++) pointsByX[i] = points[i];
034                Arrays.sort(pointsByX, Point2D.X_ORDER);
035
036                // check for coincident points
037                for (int i = 0; i < N-1; i++) {
038                        if (pointsByX[i].equals(pointsByX[i+1])) {
039                                bestDistance = 0.0;
040                                best1 = pointsByX[i];
041                                best2 = pointsByX[i+1];
042                                return;
043                        }
044                }
045
046                // sort by y-coordinate (but not yet sorted)
047                Point2D[] pointsByY = new Point2D[N];
048                for (int i = 0; i < N; i++) pointsByY[i] = pointsByX[i];
049
050                // auxiliary array
051                Point2D[] aux = new Point2D[N];
052
053                closest(pointsByX, pointsByY, aux, 0, N-1);
054        }
055
056        // find closest pair of points in pointsByX[lo..hi]
057        // precondition:  pointsByX[lo..hi] and pointsByY[lo..hi] are the same sequence of points
058        // precondition:  pointsByX[lo..hi] sorted by x-coordinate
059        // postcondition: pointsByY[lo..hi] sorted by y-coordinate
060        private double closest(Point2D[] pointsByX, Point2D[] pointsByY, Point2D[] aux, int lo, int hi) {
061                if (hi <= lo) return Double.POSITIVE_INFINITY;
062
063                int mid = lo + (hi - lo) / 2;
064                Point2D median = pointsByX[mid];
065
066                // compute closest pair with both endpoints in left subarray or both in right subarray
067                double delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
068                double delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
069                double delta = Math.min(delta1, delta2);
070
071                // merge back so that pointsByY[lo..hi] are sorted by y-coordinate
072                Merge.merge(pointsByY, aux, lo, mid, hi);
073
074                // aux[0..M-1] = sequence of points closer than delta, sorted by y-coordinate
075                int M = 0;
076                for (int i = lo; i <= hi; i++) {
077                        if (Math.abs(pointsByY[i].x() - median.x()) < delta)
078                                aux[M++] = pointsByY[i];
079                }
080
081                // compare each point to its neighbors with y-coordinate closer than delta
082                for (int i = 0; i < M; i++) {
083                        // a geometric packing argument shows that this loop iterates at most 7 times
084                        for (int j = i+1; (j < M) && (aux[j].y() - aux[i].y() < delta); j++) {
085                                double distance = aux[i].distanceTo(aux[j]);
086                                if (distance < delta) {
087                                        delta = distance;
088                                        if (distance < bestDistance) {
089                                                bestDistance = delta;
090                                                best1 = aux[i];
091                                                best2 = aux[j];
092                                                // StdOut.println("better distance = " + delta + " from " + best1 + " to " + best2);
093                                        }
094                                }
095                        }
096                }
097                return delta;
098        }
099
100        public Point2D either() { return best1; }
101        public Point2D other()  { return best2; }
102
103        public double distance() {
104                return bestDistance;
105        }
106
107
108        public static void main(String[] args) {
109                StdIn.fromFile ("data/rs1423.txt");
110
111                int N = StdIn.readInt();
112                Point2D[] points = new Point2D[N];
113                for (int i = 0; i < N; i++) {
114                        double x = StdIn.readDouble();
115                        double y = StdIn.readDouble();
116                        points[i] = new Point2D(x, y);
117                }
118                ClosestPair closest = new ClosestPair(points);
119                StdOut.println(closest.distance() + " from " + closest.either() + " to " + closest.other());
120        }
121
122}