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}