v[0:4]={(1,1),(2,1),(2.5,2.5),(3,3),(4,4)}，如何用java写出分治法求解并输出二维最接近点对坐标以及两点间距离

以下是 ChitGPT 回答：

你好，根据您的问题，我可以向您提供以下 Java 代码，用于分治法求解最接近点对坐标和两点间距离：

import java.util.Arrays;

public class ClosestPair {

private static class Point {
double x, y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
}

private static double dist(Point p1, Point p2) {
return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

private static double bruteForce(Point[] points, int start, int end) {
double minDist = Double.POSITIVE_INFINITY;
for (int i = start; i <= end; i++) {
for (int j = i + 1; j <= end; j++) {
double dist = dist(points[i], points[j]);
if (dist < minDist) {
minDist = dist;
}
}
}
return minDist;
}

private static double stripClosest(Point[] strip, int size, double d) {
double minDist = d;
Arrays.sort(strip, 0, size, (p1, p2) -> Double.compare(p1.y, p2.y));
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < minDist; j++) {
double dist = dist(strip[i], strip[j]);
if (dist < minDist) {
minDist = dist;
}
}
}
return minDist;
}

private static double closestUtil(Point[] px, Point[] py, int start, int end) {
if (end - start <= 2) {
return bruteForce(px, start, end);
}
int mid = (start + end) / 2;
Point midPoint = px[mid];
Point[] pyl = new Point[mid - start + 1];
Point[] pyr = new Point[end - mid];
int li = 0, ri = 0;
for (int i = 0; i < py.length; i++) {
if (py[i].x <= midPoint.x && li < pyl.length) {
pyl[li++] = py[i];
} else if (py[i].x > midPoint.x && ri < pyr.length) {
pyr[ri++] = py[i];
}
}
double dl = closestUtil(px, pyl, start, mid);
double dr = closestUtil(px, pyr, mid + 1, end);
double d = Math.min(dl, dr);
Point[] strip = new Point[end - start + 1];
int size = 0;
for (int i = start; i <= end; i++) {
if (Math.abs(px[i].x - midPoint.x) < d) {
strip[size++] = px[i];
}
}
double closest = stripClosest(strip, size, d);
return Math.min(d, closest);
}

public static void main(String[] args) {
Point[] points = {new Point(1, 1), new Point(2, 1), new Point(2.5, 2.5), new Point(3, 3), new Point(4, 4)};
Arrays.sort(points, (p1, p2) -> Double.compare(p1.x, p2.x));
Point[] py = Arrays.copyOf(points, points.length);
Arrays.sort(py, (p1, p2) -> Double.compare(p1.y, p2.y));
double closest = closestUtil(points, py, 0, points.length - 1);
System.out.println("最接近点对坐标为：");
for (int i = 0; i < points.length - 1; i++) {
for (int j = i + 1; j < points.length; j++) {
if (dist(points[i], points[j]) == closest) {
System.out.println("(" + points[i].x + ", " + points[i].y + ")、(" + points[j].x + ", " + points[j].y + ")");
}
}
}
System.out.println("两点间距离为：" + closest);
}
}

希望这段代码能够帮助您。