求助quq 81分wa两个点,wa的一声哭了

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

zhaoyoulan @ 2019-11-07 11:06:10

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int n;
double INF=1e15;
int fz[200100];
struct d
{
    double x,y;
}tu[200100];
bool cmp(d xx,d yy)
{
    return xx.x<yy.x;
}
double js(int x,int y)
{
    return sqrt((tu[x].x-tu[y].x)*(tu[x].x-tu[y].x)+(tu[x].y-tu[y].y)*(tu[x].y-tu[y].y));
}
double solve(int l,int r)
{
    double minn=INF;
    if(l==r)
        return INF;
    minn=min(minn,solve(l,(l+r)/2));
    minn=min(minn,solve((l+r)/2+1,r));
    int mid=(l+r)/2;
    int k=0;
    for(int i=l;i<=r;i++)
        if(js(i,mid)<minn)
            fz[++k]=i;
    for(int i=1;i<=k;i++)
        for(int j=i+1;j<=k;j++)
            if(minn>js(fz[i],fz[j]))
                minn=js(fz[i],fz[j]);
    return minn;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>tu[i].x>>tu[i].y;
    sort(tu+1,tu+n+1,cmp);
    printf("%.4f",solve(1,n));
}

by platelett @ 2020-07-08 10:56:36

@zhaoyoulan
我的情况和您一样,请问您是怎么解决的?


by bibi丶 @ 2020-12-19 12:31:22

@aa2465478971qq 请问您是怎么解决的我也是这样


|