求助大牛 10分:1个ac,剩下好多wa,re,tle
查看原帖
求助大牛 10分:1个ac,剩下好多wa,re,tle
1149836
thesadbee楼主2024/4/23 15:10

代码如下 求助各位大牛

#include<bits/stdc++.h>
using namespace std;
int n,tem[10004];
double l,r,d1,d2,dm;
int k=0;
double ans=2<<20;

struct dot
{
    int x;
    int y;
}d[1004];

bool cmp(dot p,dot q){
    if(p.x!=q.x) return p.x<q.x;
    else return p.y<q.y;
}

bool cmps(int w,int e){
    return d[w].y<d[e].y;
}

double matx(dot a,dot b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double landr(int l,int r){
    if(l==r) return 2e9;
    if(l+1==r) return matx(d[l],d[r]);
    int mid=(l+r)/2;
    d1=landr(l,mid);
    d2=landr(mid+1,r);
    dm=min(d1,d2);
    for(int i=1;i<=n;i++){
        if(abs(d[i].x-d[mid].x)<=dm){
            tem[++k]=i;
        }
    }
    sort(tem+1,tem+k+1,cmps);
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=k;j++){
            if(abs(d[i].y-d[j].y)<dm)
            ans=min(ans,matx(d[i],d[j]));
        }
    }
    return ans;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i].x>>d[i].y;
    }
    sort(d+1,d+n+1,cmp);
    l=1;
    r=n;
    printf("%.4lf\n",landr(l,r));
}
2024/4/23 15:10
加载中...