有木有能帮忙的人啊

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

秋水1024 @ 2021-07-26 20:37:12

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,s[100086],tot;
struct node{
    double x,y;
}e[200021];
bool cmp(node a,node b){
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
bool cmp1(int a,int b){
    return e[a].y<e[b].y;
}
double jl(int a,int b){
    double jl0=(e[a].x-e[b].x)*(e[a].x-e[b].x)+(e[a].y-e[b].y)*(e[a].y-e[b].y);
    return sqrt(jl0);
}
double merge(int l,int r){
    if(l==r)return double(2<<20)+0.1;
    if(l==r-1)return jl(l,r);
    int mid=(l+r)/2;
    double d=min(merge(l,mid),merge(mid+1,r));
    memset(s,0,sizeof(s));s[1]=mid;tot=1;
    for(int i=l;i<=r;i++)
        if(abs(e[mid].x-e[i].x)<=d)
            s[++tot]=i;
    sort(s+1,s+tot+1,cmp1);
    for(int i=1;i<=tot;i++)
        for(int j=i+1;j<=tot&&abs(e[j].y-e[i].y)<=d;j++){
            double d0=jl(i,j);
            if(d>d0)d=d0;
        }
//  cout<<l<<" "<<r<<" "<<d<<endl;
    return d;
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%lf%lf",&e[i].x,&e[i].y);
    //cout<<e[1].x<<e[1].y<<e[2].x<<e[2].y;
    sort(e,e+n+1, cmp);
    double ans=merge(1, n);
    printf("%.4lf\n",ans);
    return 0;
}

by 秋水1024 @ 2021-07-26 20:37:44

大红大紫的

我傻了555


by seh_sjij @ 2021-09-29 08:50:40

sort(e,e+n+1, cmp);

应为

sort(e+1,e+n+1, cmp);

|