Section introduced an algorithm for finding the closest pair of points using a divide-and-conquer approach. Implement the algorithm to meet the following requirements:

Write a program that meets the following requirements:

? Define a class named?Point?with two data fields?x?and?y?to represent a point?s?x- and?y-coordinates. Implement the?Comparable?interface for comparing the points on?x-coordinates. If two points have the same?x-coordinates, compare their?y-coordinates.

? Define a class named?CompareY?that implements?Comparator. Implement the?compare?method to compare two points on their?y-coordinates. If two points have the same?y-coordinates, compare their?x-coordinates.

? Randomly create?100?points and apply the?Arrays.sort?method to display the points in increasing order of their?x-coordinates and in increasing order of their?y-coordinates, respectively.

? Define a class named?Pair?with the data fields?p1?and?p2?to represent two points, and a method named?getDistance()?that returns the distance between the two points.

? Implement the following methods:

Transcribed Image Text:

/** Return the distance of the closest pair of points */ public static Pair getClosestPair(double[][] points) /** Return the distance of the closest pair of points */ public static Pair getClosestPair(Point[] points) /** Return the distance of the closest pair of points * in pointsOrderedOnX[low..high]. This is a recursive * method. pointsOrderedOnX and pointsOrderedOnY are * not changed in the subsequent recursive calls. */ public static Pair distance(Point[] pointsOrderedOnx, int low, int high, Point[] pointsOrderedOnY) /** Compute the distance between two points p1 and p2 */ public static double distance(Point pl, Point p2) /** Compute the distance between points (x1, y1) and (x2, y2) */ public static double distance(double x1, double y1, double x2, double y2)