第一个点就wa了,输出92009.5964,54分求助啊,进来看看呗

P1429 平面最近点对(加强版)

weird_coder @ 2020-11-23 19:41:37

#include<stdio.h>
#include<string.h>
#include<math.h>
struct node
{
    double x, y;
}a[200005];
double distance(node a, node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double min(double x,double y)
{
    return x < y ? x : y;
}
node s[200005];
int cnt = 0;
double ans = 3e10;
node t[200005];
void sort(int l, int r)
{
    int mid = (l + r) >> 1;
    if (l >= r) return;
    sort(l, mid);
    sort(mid + 1, r);
    int k = l;
    int i = l,j=mid+1;
    while (i<=mid&&j<=r)
    {
        if (a[i].y < a[j].y) t[k++] = a[i++];
        else t[k++] = a[j++];
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = t[i];
}
void sort0(int l, int r)
{
    int mid = (l + r) >> 1;
    if (l >= r) return;
    sort(l, mid);
    sort(mid + 1, r);
    int k = l;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (a[i].x < a[j].x) t[k++] = a[i++];
        else t[k++] = a[j++];
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = t[i];
}
void merge(int l, int r)
{
    int mid = (l + r) >> 1;
    double dis;
    if (l == r) return;
    if (l + 1 == r)
    {
        dis = distance(a[l], a[r]);
        if (dis < ans) ans = dis;
        return;
    }
    merge(l, mid);
    merge(mid + 1, r);
    cnt = 0;
    for (int i = l; i <= r; i++)
    {
        if (fabs(a[i].x - a[mid].x) <= ans)
        {
            s[++cnt] = a[i];
        }
    }
    sort(1, cnt);
    for(int i=1;i<=cnt;i++)
        for (int j = i + 1; j <= cnt && s[j].y - s[i].y < ans; j++)
        {
            ans = min(distance(s[i],s[j]),ans);
        }
}
int main()
{
    freopen("a.txt","r",stdin);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &a[i].x, &a[i].y);
    sort0(1, n);
    merge(1, n);
    printf("%.4lf", ans);
    return 0;
}

|