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

题目地址

题意：给出n个点，求最近的两个点距离的平方

Solution

分治法

dfs(i,j)表示在i，j上的最近点距离的平方，问题在于如何将两个区间的合并

原题解（囧仙）

对于区间长度等于2的区间，直接返回距离，等于1则返回无限

以mid为中心，|x[mid]-x[i]|<res的点都统计一遍，如果大于res，肯定不符合条件

然后将统计的点按y升序排序，从左往右遍历，看是否有|y[i]-y[j]|<res的点，计算距离然后更新res即可

这样做很快，可以做到350ms内通过样例

 1 nt dfs(int l,int r)
 2 {
 3     //cout<<l<<" "<<r<<"\n";
 4     if(r-l+1<=3)
 5     {
 6         int res=8e18;
 7         for(int i=l;i<=r;i++)
 8             for(int j=i+1;j<=r;j++)
 9                 res=min(res,dist(e[i],e[j]));
10         return res;
11     }
12     int mid=(l+r)>>1;
13     int res=min(dfs(l,mid),dfs(mid+1,r));
14     
15     
16     int cnt=0;
17     for(int i=l;i<=r;i++)
18     {
19         int o=(e[i].x-e[mid].x);
20         if(o*o>=res)continue;
21         b[++cnt]=e[i];
22 
23     }
24     sort(b+1,b+1+cnt,cmp1);
25     for(int i=1;i<=cnt;i++)
26     {
27         for(int j=i-1;j>=1;j--)
28         {
29             int yy=b[i].y-b[j].y;
30             if(yy*yy>=res)break;
31             res=min(res,dist(b[i],b[j]));
32         }
33     }
34     return res;
35     
36 }
37 
38 
39 void solve()
40 {
41     int n;scanf("%lld",&n);
42     for(int i=1;i<=n;i++)scanf("%lld%lld",&e[i].x,&e[i].y);
43     sort(e+1,e+1+n,cmp);
44     printf("%lld",dfs(1,n));
45 }