Hide Assignment Information

Instructions

Test your program with randomly generated set of points and submit the screenshot of the compile result and your execution result.

Section $22\mathrm{.}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 the classes Point and CompareY in the same way as in Programming Exercise $20\mathrm{.}4.$

$$ Define a class named Pair with the data fields p$1$ and p$2$ 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$($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 p$1$ and p$2*/$

public static double distance$($Point p$1,$ Point p$2)$

$/**$ Compute the distance between points $($x$1,$ y$1)$ and $($x$2,$ y$2)*/$

public static double distance$($double x$1,$ double y$1,$ double x$2,$ double y$2)$