java计算地球两个凸多边形距离代码

计算两个凸多边形的距离可以使用最短距离对的算法（Shortest Distance Pair Algorithm），以下是 Java 实现代码。

import java.util.*;

public class ConvexPolygonDistance {
    static final double INF = 1e9;
    
    static class Point {
        double x, y;
        
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static double dist(Point a, Point b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return Math.sqrt(dx * dx + dy * dy);
    }
    
    static double solve(Point[] p, Point[] q) {
        int n = p.length, m = q.length;
        double ans = INF;
        for (int i = 0, j = 0; i < n; i++) {
            while (j + 1 < m && (q[j + 1].y - q[j].y) > (p[i + 1].y - p[i].y)) j++;
            double d = INF;
            for (int k = j; k <= Math.min(m - 1, j + 1); k++) {
                d = Math.min(d, dist(p[i], q[k]));
            }
            ans = Math.min(ans, d);
        }
        return ans;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        Point[] p = new Point[n], q = new Point[m];
        for (int i = 0; i < n; i++) {
            p[i] = new Point(sc.nextDouble(), sc.nextDouble());
        }
        for (int i = 0; i < m; i++) {
            q[i] = new Point(sc.nextDouble(), sc.nextDouble());
        }
        double ans = Math.min(solve(p, q), solve(q, p));
        System.out.printf("%.6f", ans);
    }
}

输入格式：

第一行包含两个整数 $n$ 和 $m$，分别表示两个凸多边形的顶点数。

接下来 $n$ 行，每行包含两个实数 $x_i$ 和 $y_i$，表示第一个凸多边形的一个顶点的坐标。

接下来 $m$ 行，每行包含两个实数 $x_i$ 和 $y_i$，表示第二个凸多边形的一个顶点的坐标。

输出格式：

输出两个凸多边形的最小距离，保留六位小数。