(Closest pair of points) Section 22.8 introduced an algorithm for finding the closest pair of points using a divide-and-conquer approach. Implement the algorithm to meet the following requirements: 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: /** 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(Point2D[] 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(Point2D[] pointsOrderedOnX, int low, int high, Point2D[] pointsOrderedOnY) /** Compute the distance between two points p1 and p2 */ public static double distance(Point2D p1, Point2D p2) /** Compute the distance between points (x1, y1) and (x2, y2) */ public static double distance(double x1, double y1, double x2, double y2)

My Code its not working

package closestpair;

public class ClosestPair {

private Point2D best1, best2; private double bestDistance = Double.POSITIVE_INFINITY; public ClosestPair(Point2D[] points) { if (points == null) throw new IllegalArgumentException ("constructor argument is null"); for (int i=0; i { if(points[i]==null) throw new IllegalArgumentException("array element "+i+"is null"); } int n=points.lenght; if (n<=1) return; Point2D[] pointsByx = new Point2D[n]; for (int i=0; i { if(pointsByx[i].equals(pointsByx[i+1])) { bestDistance=0.0; best1=pointsByx[i]; best2=pointsByx[i=1]; return; } } Point2D[] pointsByy=new Point2D[n]; for (int i=0; i pointsByy[i]=pointsByx[i]; Point2D[] aux=new Point2d[n]; closest (pointsByx, pointsByy, aux, 0, n-1); }

private double closest(Point2D[] pointsByX, Point2D[] pointsByY, Point2D[] aux, int lo, int hi) { if (hi <= lo) return Double.POSITIVE_INFINITY; int mid = lo + (hi - lo) / 2; Point2D median = pointsByX[mid]; double delta1 = closest(pointsByX, pointsByY, aux, lo, mid); double delta2 = closest(pointsByX, pointsByY, aux, mid+1, hi); double delta = Math.min(delta1, delta2); int m = 0; for (int i = lo; i <= hi; i++) { if (Math.abs(pointsByY[i].x() - median.x()) < delta) aux[m++] = pointsByY[i]; } for (int i = 0; i < m; i++) { for (int j = i+1; (j < m) && (aux[j].y() - aux[i].y() < delta); j++) { double distance = aux[i].distanceTo(aux[j]); if (distance < delta) { delta = distance; if (distance < bestDistance) { bestDistance = delta; best1 = aux[i]; best2 = aux[j]; } } } return delta; } public Point2D either(){ return best1; } public Point2D other(){ return best2; } public double distance(){ return bestDistance; } private static boolean less(Comparable v, Comparable w){ return v.compareTo(w) < 0; } private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { for (int k = lo; k <= hi; k++){ aux[k] = a[k]; } } int i = lo, j = mid+1; for (int k = lo; k <= hi; k++){ if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } public static void main(String[] args){ int n = StdIn.readInt(); Point2D[] points = new Point2D[n]; for (int i = 0; i < n; i++) { double x = StdIn.readDouble(); double y = StdIn.readDouble(); points[i] = new Point2D(x, y); } ClosestPair closest = new ClosestPair(points); StdOut.println(closest.distance() + " from " + closest.either() + " to " + closest.other()); } }