某司OA2 Closest Pair of Points
某A公司OA2的题目，给了平面上一些点的坐标，求这些点里面距离最近的两个点之间的距离。
自己想只能想到brute force的O(N^2)，然后看了别人说这是divide and conquer的经典题，我真是基础太差了完全不知道orz 于是就参考了这两个link：https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/是O(n*(logn)^2)的做法，https://www.geeksforgeeks.org/closest-pair-of-points-onlogn-implementation/是O(nlogn)的做法，其实后者就是在前者的基础上多优化了一个小步骤。
说到分治就大概能想到总体思路了：把所有点根据x坐标通过中线分成两部分，分别求两部分之中距离最小的点，然后把两部分合一起，求出整体的最小值。然鹅，还有一种情况就是整体的距离最小的两个点分别在刚刚分开的两部分之中，这种情况就需要单独考虑了，于是在分治法中求最小值的时候还需要额外考虑这种情况。具体这种情况要怎么处理：首先我们考虑到，我们已经求出了左右两边分别的最小值之中的更小值（称之为d），那么对于分散在中线两边的点，如果要比这个值更小的话，顶多只能在(mid - d, mid + d)的坐标范围内找，所以我们先把这些点挑出来放进一个叫做strip的数组里。对于stripe里的每个点，我们先根据y坐标从小到大排序，然后双重循环疑似brute force来找最小值。这里的brute force就很tricky了，虽然是双重循环听起来是个O(n^2)，但是，内层循环的循环停止条件我们可以加上“当两个点的y坐标之差>d时就可以停止了”，毕竟再大就不可能更小了，于是通过数学证明可以得出内层循环中顶多只需要examine 7个点，证明我就懒得看了orz 所以这个循环的时间复杂度其实是O(n)。
另外在分治的时候还可以考虑到，如果当前的数组里只有不超过3个点，那么我们可以直接采用brute force找最小，还更省事儿。所以在分治的里面加了个判断如果元素个数<=3就直接brute force。
所以整体这个做法的时间复杂度，首先是先sort了一遍，sort是O(nlogn)，然后分治。分治的表达式是T(n) = 2T(n/2) + O(n) + O(n) + O(n)，第一个O(n)是把按y坐标排好序的所有点根据中线分成两边用的（如果是用的非优化方法就的话这一步就是sort这个strip，时间复杂度就变成了O(nlogn)），第二个O(n)是求strip数组用的，第三个O(n)是在strip中找最小用的。最后化简得到T(n)=2T(n/2)+O(n)，各种数学推导（我不会）一下最后的时间复杂度就是O(nlogn)了。如果是非优化方法的话，化简后应该是T(n)=2T(n/2)+O(nlogn)，最后推导完就是O(n*(longn)^2)。
代码：
import java.util.*;
public class ClosestSquaredDistance {
static class Point {
public int x;
public int y;
Point(int newX, int newY) {
x = newX;
y = newY;
}
}
/**
* Squared Distance: (x1 - x2) ^ 2 + (y1 - y2) ^ 2
* Consider them to be in the same position if distance is 0
*/
public static long closestSquaredDistanceBruteForce(int numRobots, List<Integer> positionX, List<Integer> positionY) {
Point[] points = buildPoints(numRobots, positionX, positionY);
return bruteForceSearch(points, numRobots);
}
public static Point[] buildPoints(int numRobots, List<Integer> positionX, List<Integer> positionY) {
Point[] coordinates = new Point[numRobots];
for (int i = 0; i < numRobots; i++) {
Point p = new Point(positionX.get(i), positionY.get(i));
coordinates[i] = p;
}
return coordinates;
}
public static long bruteForceSearch(Point[] points, int numRobots) {
long result = Integer.MAX_VALUE;
for (int i = 0; i < numRobots; i++) {
for (int j = i + 1; j < numRobots; j++) {
long distance = calculateDistance(points[i], points[j]);
if (distance < result && distance != 0) {
result = distance;
}
}
}
return result;
}
public static long calculateDistance(Point p1, Point p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
public static void printPoints(Point[] points) {
for (Point p : points) {
System.out.print("(" + p.x + ", " + p.y + "); ");
}
System.out.println();
}
/**
* O(n(longn)^2): https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/
* O(nlogn): https://www.geeksforgeeks.org/closest-pair-of-points-onlogn-implementation/?ref=rp
*
* 1) We sort all points according to x coordinates.
* 2) Divide all points in two halves.
* 3) Recursively find the smallest distances in both subarrays.
* 4) Take the minimum of two smallest distances. Let the minimum be d.
* 5) Create an array strip[] that stores all points which are at most d distance away from the middle line dividing the two sets.
* 6) Find the smallest distance in strip[].
* 7) Return the minimum of d and the smallest distance calculated in above step 6.
*/
public static long closestSquaredDistance(int numRobots, List<Integer> positionX, List<Integer> positionY) {
Point[] coordinates = buildPoints(numRobots, positionX, positionY);
Arrays.sort(coordinates, Comparator.comparingInt(a -> a.x));
Point[] sortByX = Arrays.copyOf(coordinates, numRobots);
Arrays.sort(coordinates, Comparator.comparingInt(a -> a.y));
Point[] sortByY = Arrays.copyOf(coordinates, numRobots);
System.out.print("sort by x: ");
printPoints(sortByX);
System.out.print("sort by y: ");
printPoints(sortByY);
return closestUtil(numRobots, sortByX, sortByY);
}
/**
* The main divide and conquer function
*/
public static long closestUtil(int numRobots, Point[] sortByX, Point[] sortByY) {
if (numRobots <= 3) {
return bruteForceSearch(sortByX, numRobots);
}
// get the mid point
int mid = numRobots / 2;
Point midPoint = sortByX[mid];
// divide points in y sorted array around the vertical line
Point[] yLeft = new Point[mid];
Point[] yRight = new Point[numRobots - mid];
int indexLeft = 0;
int indexRight = 0;
for (Point p : sortByY) {
if (p.x <= midPoint.x && indexLeft < mid) {
yLeft[indexLeft] = p;
indexLeft++;
} else {
yRight[indexRight] = p;
indexRight++;
}
}
System.out.print("yLeft: ");
printPoints(yLeft);
System.out.print("yRight: ");
printPoints(yRight);
// divide points in x sorted array
Point[] xLeft = Arrays.copyOfRange(sortByX, 0, mid);
System.out.print("xLeft: ");
printPoints(xLeft);
Point[] xRight = Arrays.copyOfRange(sortByX, mid, numRobots);
System.out.print("xRight: ");
printPoints(xRight);
// divide and conquer
long distLeft = closestUtil(mid, xLeft, yLeft);
System.out.println("distLeft: " + distLeft);
long distRight = closestUtil(numRobots - mid, xRight, yRight);
System.out.println("distRight: " + distRight);
long shorter = Math.min(distLeft, distRight);
// build strip[] to contain points closer than d to the line passing through the mid point
List<Point> strip = new ArrayList<>();
for (Point p : sortByY) {
if (Math.abs(p.x - midPoint.x) < shorter) {
strip.add(p);
}
}
return stripClosest(strip, shorter);
}
public static long stripClosest(List<Point> strip, long distance) {
long min = distance;
for (int i = 0; i < strip.size(); i++) {
for (int j = i + 1; j < strip.size() && (strip.get(j).y - strip.get(i).y < distance); j++) {
min = Math.min(calculateDistance(strip.get(i), strip.get(j)), min);
}
}
System.out.println("strip closest: " + min);
return min;
}
public static void main(String[] args) {
// Integer[] x = {0, 1, 2};
// Integer[] y = {0, 1, 4};
Integer[] x = {2, 12, 40, 5, 12, 3};
Integer[] y = {3, 30, 50, 1, 10, 4};
// {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
System.out.println(closestSquaredDistance(6, Arrays.asList(x), Arrays.asList(y)));
}
}