有大佬看看我写的分治哪儿T了嘛(哭

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

明明明明子丶 @ 2019-10-04 20:03:49

窝觉得跟分治题解写的一模一样哇

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
struct Node{
    double x,y;
}a[N],t[N];
bool cmpx(const Node &a,const Node &b){
    if(fabs(a.x-b.x)<=1e-5)
        return a.y<b.y;
    return a.x<b.x;
}
bool cmpy(const Node &a,const Node &b){
    if(fabs(a.y-b.y)<=1e-5)
        return a.x<b.x;
    return a.y<b.y;
}
double ans=1e30;
double dis(int x,int y){
    return (t[x].x-t[y].x)*(t[x].x-t[y].x)+(t[x].y-t[y].y)*(t[x].y-t[y].y);
}
double dis2(int x,int y){
    return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
int tot;
void fz(int l,int r){
    if(l>=r)return;
    int m=(l+r)>>1;
    fz(l,m);
    fz(m+1,r);
    double mx=a[m].x;
    tot=0;
    //t[tot]=a[m];
    for(int i=l;i<=r;i++)
        if(fabs(mx-a[i].x)<=ans+1e-5) t[++tot]=a[i];
    sort(t+1,t+tot+1,cmpy);
    for(int i=1;i<tot;i++)
        for(int j=i+1;j<=tot&&t[j].y-t[i].y<=ans;j++)
            ans=min(ans,dis(i,j));
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmpx);
    fz(1,n);
    printf("%.4lf\n",sqrt(ans));
    return 0;
}

by lc_lca @ 2019-10-04 20:23:08

重构代码/滑稽


by xwmwr @ 2019-10-05 16:00:59

吐槽一下,为啥会有double dis2(int x,int y)这个函数?


|