P1257平面上的最接近点对

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 
 6 const double INF=0x3f3f3fLL;
 7 const int MAXN=200010;
 8 
 9 int n;
10 
11 int t[MAXN];
12 
13 struct node {
14     double x,y;
15     friend inline bool operator < (node x,node y) {
16         if(x.x==y.x) return x.y<y.y;
17         return x.x<y.x;
18     }
19 };
20 node E[MAXN];
21 
22 inline double cal(int i,int j) {
23     double x=(E[i].x-E[j].x)*(E[i].x-E[j].x);
24     double y=(E[i].y-E[j].y)*(E[i].y-E[j].y);
25     return sqrt(x+y);
26 }
27 
28 inline bool cmp(int x,int y) {
29     return E[x].y<E[y].y;
30 }
31 
32 inline double merge(int l,int r) {
33     double d=INF;
34     if(l==r) return d;
35     if(l+1==r) return cal(l,r);
36     int mid=(l+r)>>1;
37     double disl=merge(l,mid);
38     double disr=merge(mid+1,r);
39     d=disldisl:disr;
40     int tot=0;
41     for(int i=l;i<=r;++i) 
42       if(abs(E[mid].x-E[i].x)<=d) 
43         t[++tot]=i;
44     std::sort(t+1,t+1+tot,cmp);
45     for(int i=1;i<=tot;++i)
46       for(int j=i+1;j<=tot&&E[t[j]].y-E[t[i]].yj) {
47           double dis=cal(t[i],t[j]);
48           d=dd:dis;
49       }
50     return d;
51 }
52 
53 int hh() {
54     scanf("%d",&n);
55     for(int i=1;i<=n;++i) 
56       scanf("%lf%lf",&E[i].x,&E[i].y);
57     std::sort(E+1,E+1+n);
58     double ans=merge(1,n);
59     printf("%.4lf\n",ans);
60     return 0;
61 }
62 
63 int sb=hh();
64 int main(int argc,char**argv) {;}