真的没想到这样也有90...怕不是数据太水或者我RP==Inf

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

一秒 @ 2018-10-19 16:26:25

#include<bits/stdc++.h>
using namespace std;
struct mmp{
        double x,y;
}s[200010];
inline bool cmp(mmp a,mmp b){
        if(a.x!=b.x) return a.x<b.x;
        return a.y<b.y;
}
double dfs(int l,int r){
        if(l==r)return 9999999;
        if(r==l+1)return (double)sqrt((s[l].x-s[r].x)*(s[l].x-s[r].x)+(s[l].y-s[r].y)*(s[l].y-s[r].y));
        int mid=(l+r)>>1;
        double ans1=min(dfs(l,mid),dfs(mid+1,r)),len=s[mid+1].x-s[mid].x;
        if(len<ans1)return min(sqrt((s[mid].x-s[mid+1].x)*(s[mid].x-s[mid+1].x)+(s[mid].y-s[mid+1].y)*(s[mid].y-s[mid+1].y)),ans1);
        else return ans1;
}
int main(){
        int n;cin>>n;
        for(int q=1;q<=n;q++){
                scanf("%lf%lf",&s[q].x,&s[q].y);
        }
        sort(s+1,s+n+1,cmp);
        printf("%.4lf",dfs(1,n));
}

by HuaJi_360 @ 2020-01-23 15:13:29

tql %%%

OTZ


|