001package algs91; // section 9.8
002import algs12.Point2D;
003import stdlib.*;
004/* ***********************************************************************
005 *  Compilation:  javac FarthestPair.java
006 *  Execution:    java FarthestPair < input.txt
007 *  Dependencies: GrahamScan.java Point2D.java
008 *
009 *  Given a set of N points in the plane, find the farthest pair
010 *  (equivalently, compute the diameter of the set of points).
011 *
012 *  Computes the convex hull of the set of points and using the
013 *  rotating callipers method to find all antipodal point pairs
014 *  and the farthest pair.
015 *
016 *  % java FarthestPair < rs1423.txt
017 *  7748.838622658237 from (24690.0, 216.0) to (32420.0, 756.0)
018 *************************************************************************/
019
020public class FarthestPair {
021
022        // farthest pair of points and distance
023        private Point2D best1, best2;
024        private double bestDistance = Double.NEGATIVE_INFINITY;
025
026        public FarthestPair(Point2D[] points) {
027                GrahamScan graham = new GrahamScan(points);
028
029                // single point
030                if (points.length <= 1) return;
031
032                // number of points on the hull
033                int M = 0;
034                for (Point2D p : graham.hull())
035                        M++;
036
037                // the hull, in counterclockwise order
038                Point2D[] hull = new Point2D[M+1];
039                int m = 1;
040                for (Point2D p : graham.hull()) {
041                        hull[m++] = p;
042                }
043
044                // all points are equal
045                if (M == 1) return;
046
047                // points are collinear
048                if (M == 2) {
049                        best1 = hull[1];
050                        best2 = hull[2];
051                        bestDistance = best1.distanceTo(best2);
052                        return;
053                }
054
055                // k = farthest vertex from edge from hull[1] to hull[M]
056                int k = 2;
057                while (Point2D.area2(hull[M], hull[k+1], hull[1]) > Point2D.area2(hull[M], hull[k], hull[1])) {
058                        k++;
059                }
060
061                int j = k;
062                for (int i = 1; i <= k; i++) {
063                        // StdOut.println("hull[i] + " and " + hull[j] + " are antipodal");
064                        if (hull[i].distanceTo(hull[j]) > bestDistance) {
065                                best1 = hull[i];
066                                best2 = hull[j];
067                                bestDistance = hull[i].distanceTo(hull[j]);
068                        }
069                        while ((j < M) && Point2D.area2(hull[i], hull[j+1], hull[i+1]) > Point2D.area2(hull[i], hull[j], hull[i+1])) {
070                                j++;
071                                // StdOut.println(hull[i] + " and " + hull[j] + " are antipodal");
072                                double distance = hull[i].distanceTo(hull[j]);
073                                if (distance > bestDistance) {
074                                        best1 = hull[i];
075                                        best2 = hull[j];
076                                        bestDistance = hull[i].distanceTo(hull[j]);
077                                }
078                        }
079                }
080        }
081
082        public Point2D either()    { return best1;        }
083        public Point2D other()     { return best2;        }
084        public double distance()   { return bestDistance; }
085
086
087        public static void main(String[] args) {
088                StdIn.fromFile ("data/rs1423.txt");
089
090                int N = StdIn.readInt();
091                Point2D[] points = new Point2D[N];
092                for (int i = 0; i < N; i++) {
093                        int x = StdIn.readInt();
094                        int y = StdIn.readInt();
095                        points[i] = new Point2D(x, y);
096                }
097                FarthestPair farthest = new FarthestPair(points);
098                StdOut.println(farthest.distance() + " from " + farthest.either() + " to " + farthest.other());
099        }
100
101}