POJ 3714 平面最近点对-白红宇

POJ 3714 平面最近点对

阅读量：4682 次

发布时间：2019-06-09

本文共 3556 字，大约阅读时间需要 11 分钟。

题意：

分为两种点，求两种点之间的平面最近点对

题解：

分治法。这个怎么暴力分治都能过。。

吐槽：我用了g++ tle+wa，毛线。。。

View Code

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 8 #define N 222222 9 #define EPS 1e-710 #define INF 1e1511 12 using namespace std;13 14 struct PO15 {16 bool fg;17 double x,y;18 }p[N];19 20 int n,q1[N],q2[N];21 22 inline bool cmp(const PO &a,const PO &b)23 {24 return a.x
            
             EPS) return 1;30 else if(x<-EPS) return -1;31 return 0;32 }33 34 inline double get_dis(PO &a,PO &b)35 {36 if(a.fg==b.fg) return INF;37 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));38 }39 40 inline double min(double a,double b)41 {42 if(doublecmp(a-b)<=0) return a;43 return b;44 }45 46 inline void read()47 {48 scanf("%d",&n);49 for(int i=1;i<=n;i++) 50 {51 scanf("%lf%lf",&p[i].x,&p[i].y);52 p[i].fg=1;53 }54 for(int i=n+1;i<=(n<<1);i++)55 {56 scanf("%lf%lf",&p[i].x,&p[i].y);57 p[i].fg=0;58 }59 n<<=1;60 }61 62 inline double getmindis(int l,int r)63 {64 if(l==r) return INF;65 if(l+1==r) return get_dis(p[l],p[r]);66 int mid=(l+r)>>1;67 double lmindis=getmindis(l,mid);68 double rmindis=getmindis(mid+1,r);69 double mindis=min(lmindis,rmindis);70 int cnt1=0,cnt2=0;71 72 for(int i=mid;i>=l;i--)73 {74 if(doublecmp(mindis-(p[mid].x-p[i].x))<=0) break;75 else if(doublecmp(mindis-fabs(p[mid].y-p[i].y))>=0) q1[++cnt1]=i;76 }77 for(int i=mid+1;i<=r;i++)78 {79 if(doublecmp(mindis-(p[i].x-p[mid].x))<=0) break;80 else if(doublecmp(mindis-fabs(p[mid].y-p[i].y))>=0) q2[++cnt2]=i;81 }82 for(int i=1;i<=cnt1;i++)83 for(int j=1;j<=cnt2;j++)84 mindis=min(mindis,get_dis(p[q1[i]],p[q2[j]]));85 return mindis;86 }87 88 inline void go()89 {90 sort(p+1,p+1+n,cmp);91 printf("%.3lf\n",getmindis(1,n));92 }93 94 int main()95 {96 int cas; scanf("%d",&cas);97 while(cas--) read(),go();98 return 0;99 }

上面那个跑的慢

这题考虑精度反而跪了。。。。无语。。。

ZOJ 2107/HDU 1007

View Code

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 8 #define N 2222222 9 #define EPS 1e-710 #define INF 1e1011 12 using namespace std;13 14 struct PO15 {16 double x,y;17 }p[N],q[N];18 19 int n;20 21 inline bool cmpx(const PO &a,const PO &b)22 {23 return a.x
            
             EPS) return 1;34 else if(x<-EPS) return -1;35 return 0;36 }37 38 inline double get_dis(PO &a,PO &b)39 {40 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));41 }42 43 inline double min(double a,double b)44 {45 if(doublecmp(a-b)<=0) return a;46 return b;47 }48 49 inline void read()50 {51 for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);52 }53 54 inline double getmindis(int l,int r)55 {56 if(l+1==r) return get_dis(p[l],p[r]);57 if(l+2==r) return min(get_dis(p[l],p[l+1]),min(get_dis(p[l+1],p[r]),get_dis(p[l],p[r])));58 int mid=(l+r)>>1;59 double mindis=min(getmindis(l,mid),getmindis(mid+1,r));60 int cnt=0;61 for(int i=l;i<=r;i++)62 if(doublecmp(mindis-fabs(p[i].x-p[mid].x))>=0) q[++cnt]=p[i];63 sort(q+1,q+1+cnt,cmpy);64 for(int i=1;i<=cnt;i++)65 for(int j=i+1;j<=cnt;j++)66 {67 if(q[j].y-q[i].y>=mindis) break;68 //if(doublecmp(p[j].y-p[i].y-mindis)>=0) break;69 mindis=min(mindis,get_dis(q[i],q[j]));70 }71 return mindis;72 }73 74 inline void go()75 {76 sort(p+1,p+1+n,cmpx);77 printf("%.2lf\n",getmindis(1,n)*0.5);78 }79 80 int main()81 {82 while(scanf("%d",&n),n) read(),go();83 return 0;84 }