Package edu.princeton.cs.algs4
Class FarthestPair
 Object

 edu.princeton.cs.algs4.FarthestPair

public class FarthestPair extends Object
TheFarthestPair
data type computes the farthest pair of points in a set of n points in the plane and provides accessor methods for getting the farthest pair of points and the distance between them. The distance between two points is their Euclidean distance.This implementation computes the convex hull of the set of points and uses the rotating calipers method to find all antipodal point pairs and the farthest pair. It runs in O(n log n) time in the worst case and uses O(N) extra space. See also
ClosestPair
andGrahamScan
.For additional documentation, see Section 9.9 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description FarthestPair(Point2D[] points)
Computes the farthest pair of points in the specified array of points.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double
distance()
Returns the Euclidean distance between the farthest pair of points.Point2D
either()
Returns one of the points in the farthest pair of points.static void
main(String[] args)
Unit tests theFarthestPair
data type.Point2D
other()
Returns the other point in the farthest pair of points.



Constructor Detail

FarthestPair
public FarthestPair(Point2D[] points)
Computes the farthest pair of points in the specified array of points. Parameters:
points
 the array of points Throws:
IllegalArgumentException
 ifpoints
isnull
or if any entry inpoints[]
isnull


Method Detail

either
public Point2D either()
Returns one of the points in the farthest pair of points. Returns:
 one of the two points in the farthest pair of points;
null
if no such point (because there are fewer than 2 points)

other
public Point2D other()
Returns the other point in the farthest pair of points. Returns:
 the other point in the farthest pair of points
null
if no such point (because there are fewer than 2 points)

distance
public double distance()
Returns the Euclidean distance between the farthest pair of points. This quantity is also known as the diameter of the set of points. Returns:
 the Euclidean distance between the farthest pair of points
Double.POSITIVE_INFINITY
if no such pair of points exist (because there are fewer than 2 points)

main
public static void main(String[] args)
Unit tests theFarthestPair
data type. Reads in an integern
andn
points (specified by their x and ycoordinates) from standard input; computes a farthest pair of points; and prints the pair to standard output. Parameters:
args
 the commandline arguments

