package algs91; // section 9.8
import stdlib.*;
import java.util.Arrays;
import algs12.Point2D;
import algs22.Merge;
/* ***********************************************************************
 *  Compilation:  javac ClosestPair.java
 *  Execution:    java ClosestPair < input.txt
 *  Dependencies: Point2D.java
 *
 *  Given N points in the plane, find the closest pair in N log N time.
 *
 *  Note: could speed it up by comparing square of Euclidean distances
 *  instead of Euclidean distances.
 *
 *  % java ClosestPair < rs1423.txt
 *  15.0 from (11364.0, 12693.0) to (11373.0, 12705.0)
 *
 *************************************************************************/


public class ClosestPair {
	// closest pair of points and their Euclidean distance
	private Point2D best1, best2;
	private double bestDistance = Double.POSITIVE_INFINITY;

	public ClosestPair(Point2D[] points) {
		int N = points.length;
		if (N <= 1) return;

		// sort by x-coordinate (breaking ties by y-coordinate)
		Point2D[] pointsByX = new Point2D[N];
		for (int i = 0; i < N; i++) pointsByX[i] = points[i];
		Arrays.sort(pointsByX, Point2D.X_ORDER);

		// check for coincident points
		for (int i = 0; i < N-1; i++) {
			if (pointsByX[i].equals(pointsByX[i+1])) {
				bestDistance = 0.0;
				best1 = pointsByX[i];
				best2 = pointsByX[i+1];
				return;
			}
		}

		// sort by y-coordinate (but not yet sorted)
		Point2D[] pointsByY = new Point2D[N];
		for (int i = 0; i < N; i++) pointsByY[i] = pointsByX[i];

		// auxiliary array
		Point2D[] aux = new Point2D[N];

		closest(pointsByX, pointsByY, aux, 0, N-1);
	}

	// find closest pair of points in pointsByX[lo..hi]
	// precondition:  pointsByX[lo..hi] and pointsByY[lo..hi] are the same sequence of points
	// precondition:  pointsByX[lo..hi] sorted by x-coordinate
	// postcondition: pointsByY[lo..hi] sorted by y-coordinate
	private double closest(Point2D[] pointsByX, Point2D[] pointsByY, Point2D[] aux, int lo, int hi) {
		if (hi <= lo) return Double.POSITIVE_INFINITY;

		int mid = lo + (hi - lo) / 2;
		Point2D median = pointsByX[mid];

		// compute closest pair with both endpoints in left subarray or both in right subarray
		double delta1 = closest(pointsByX, pointsByY, aux, lo, mid);
		double delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi);
		double delta = Math.min(delta1, delta2);

		// merge back so that pointsByY[lo..hi] are sorted by y-coordinate
		Merge.merge(pointsByY, aux, lo, mid, hi);

		// aux[0..M-1] = sequence of points closer than delta, sorted by y-coordinate
		int M = 0;
		for (int i = lo; i <= hi; i++) {
			if (Math.abs(pointsByY[i].x() - median.x()) < delta)
				aux[M++] = pointsByY[i];
		}

		// compare each point to its neighbors with y-coordinate closer than delta
		for (int i = 0; i < M; i++) {
			// a geometric packing argument shows that this loop iterates at most 7 times
			for (int j = i+1; (j < M) && (aux[j].y() - aux[i].y() < delta); j++) {
				double distance = aux[i].distanceTo(aux[j]);
				if (distance < delta) {
					delta = distance;
					if (distance < bestDistance) {
						bestDistance = delta;
						best1 = aux[i];
						best2 = aux[j];
						// StdOut.println("better distance = " + delta + " from " + best1 + " to " + best2);
					}
				}
			}
		}
		return delta;
	}

	public Point2D either() { return best1; }
	public Point2D other()  { return best2; }

	public double distance() {
		return bestDistance;
	}


	public static void main(String[] args) {
		StdIn.fromFile ("data/rs1423.txt");

		int N = StdIn.readInt();
		Point2D[] points = new Point2D[N];
		for (int i = 0; i < N; i++) {
			double x = StdIn.readDouble();
			double y = StdIn.readDouble();
			points[i] = new Point2D(x, y);
		}
		ClosestPair closest = new ClosestPair(points);
		StdOut.println(closest.distance() + " from " + closest.either() + " to " + closest.other());
	}

}