81分的二分 恳求巨佬指点QwQ

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

反手一只MJJ @ 2019-07-25 11:54:26

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<math.h>
using namespace std;
struct note{
    double x,y;
    friend bool operator < (note a,note A){
        if(a.x==A.x)
        return a.y>A.y;
        return a.x<A.x;
    }//x小的排前,x同则y大排前
}dian[200002]={0};//点
int n;
inline double minn(double a,double A){if(A-a>0)return a;return A;}
inline double dist(int l,int r){
    double X=(dian[l].x-dian[r].x)*(dian[l].x-dian[r].x);
    double Y=(dian[l].y-dian[r].y)*(dian[l].y-dian[r].y);
    return sqrt(Y+X);
}//算距离
inline double dct(int l,int r){
    if(r-l==1){return 100000007;}
    if(r-l==2){return dist(l+1,r);}//二分的两种情况
    int mid=(l+r)>>1;
    double d1=dct(l,mid);//算二分左边
    double d2=dct(mid,r);//算二分右边
    double d=minn(d1,d2);
    double tmp=100000007;//下面是算二分中间4或3个点,共4条或2条边。
    if(mid-l==2){
        tmp=minn(tmp,dist(mid-1,mid+2));
        tmp=minn(tmp,dist(mid-1,mid+1));
    }
    tmp=minn(tmp,dist(mid,mid+1));
    tmp=minn(tmp,dist(mid,mid+2));
    return minn(d,tmp);
}
int main(){
    n=rd;
    for(int i=1;i<=n;i++)
    scanf("%lf%lf",&dian[i].x,&dian[i].y);
    sort(dian+1,dian+1+n);
    printf("%0.4lf",dct(0,n));
    return 0;
}

感谢巨佬DAQ


by 白菜道士 @ 2019-08-25 20:54:28

@反手一只MJJ 看我的题解


|