Package edu.princeton.cs.algs4
Class ClosestPair
 Object

 edu.princeton.cs.algs4.ClosestPair

public class ClosestPair extends Object
TheClosestPair
data type computes a closest pair of points in a set of n points in the plane and provides accessor methods for getting the closest pair of points and the distance between them. The distance between two points is their Euclidean distance.This implementation uses a divideandconquer algorithm. It runs in O(n log n) time in the worst case and uses O(n) extra space.
See also
FarthestPair
.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 ClosestPair(Point2D[] points)
Computes the closest 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 closest pair of points.Point2D
either()
Returns one of the points in the closest pair of points.static void
main(String[] args)
Unit tests theClosestPair
data type.Point2D
other()
Returns the other point in the closest pair of points.



Constructor Detail

ClosestPair
public ClosestPair(Point2D[] points)
Computes the closest 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 closest pair of points. Returns:
 one of the two points in the closest 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 closest pair of points. Returns:
 the other point in the closest 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 closest pair of points. Returns:
 the Euclidean distance between the closest 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 theClosestPair
data type. Reads in an integern
andn
points (specified by their x and ycoordinates) from standard input; computes a closest pair of points; and prints the pair to standard output. Parameters:
args
 the commandline arguments

