最近点对问题

2024-08-14

求解计算几何中的最近点对问题

#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define SUB -INF - 1
using namespace std;
const double INF = 1e20;
const int N = 100010;
int sgn(double x)
{
    if (fabs(x) < EPS)
        return 0;
    else
        return x < 0 ? -1 : 1;
}
struct Point
{
    double x, y;
};
double Distance(Point A, Point B) { return hypot(A.x - B.x, A.y - B.y); }
bool cmpxy(Point A, Point B) { return sgn(A.x - B.x) < 0 || (sgn(A.x - B.x) == 0 && sgn(A.y - B.y) < 0); }
bool cmpy(Point A, Point B) { return sgn(A.y - B.y) < 0; }
Point p[N], tmp_p[N];
double Closest_Pair(int left, int right)
{
    double dis = INF;
    if (left == right)
        return dis;
    if (left + 1 == right)
        return Distance(p[left], p[right]);
    int mid = (left + right) / 2;
    double d1 = Closest_Pair(left, mid);
    double d2 = Closest_Pair(mid + 1, right);
    dis = min(d1, d2);
    int k = 0;
    for (int i = left; i <= right; i++)
        if (fabs(p[mid].x - p[i].x) <= dis)
            tmp_p[k++] = p[i];
    sort(tmp_p, tmp_p + k, cmpy);
    for (int i = 0; i < k; i++)
        for (int j = i + 1; j < k; j++)
        {
            if (tmp_p[j].y - tmp_p[i].y >= dis)
                break;
            dis = min(dis, Distance(tmp_p[i], tmp_p[j]));
        }
    return dis;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &p[i].x, &p[i].y);
    sort(p, p + n, cmpxy);
    printf("%.4lf\n", Closest_Pair(0, n - 1));
    return 0;
}