[POJ3714]Raid（最近点对问题【分治】）

传送门

---

题意就是寻找两个集合中的点的最近点对。
kd-tree？？我不会啊。。然后去膜大佬了
找最近点对的经典做法是分治，首先按照x坐标排序，把一大块分成左右两块，分别在左右两块里找最近点对，但是如果这个点对横跨两块的话他一定在(mid的横坐标-d)和(mid的横坐标+d)【d是当前找到的最近点对距离】之间要不然他一定不是最近的，然后暴力找即可，可以再按y坐标排序优化复杂度。也许复杂度是O(NlogN)$O(NlogN)$？？？

---

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=200010;
const double INF=1e10;
struct point
{
    double x, y;
    int f;
}p[maxn];

double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
bool cmp1(point a,point b){return a.x<b.x;}
bool cmp2(int a,int b){return p[a].y<p[b].y;}
int tmp[maxn];
double get(int l,int r)//分治找最近点对 
{
    if(r==l+1)//只有两个点 
    {
        if(p[l].f==p[r].f) return INF;
        else return dis(p[l],p[r]);
    }
    else if(r==l+2)//有三个点，分别判断情况 
    {
        if(p[l].f==p[l+1].f)
        {
            if(p[l+1].f==p[l+2].f) return INF;
            else return min(dis(p[l],p[l+2]),dis(p[l+1],p[l+2]));
        }
        else
        {
            if(p[l].f==p[l+2].f) return min(dis(p[l],p[l+1]),dis(p[l+1],p[l+2]));
            else return min(dis(p[l],p[l+1]),dis(p[l],p[l+2]));
        }
        return min(dis(p[l],p[l+1]),min(dis(p[l+1],p[l+2]),dis(p[l],p[l+2])));
    }
    int mid=(l+r)/2;
    double d=min(get(l,mid),get(mid+1,r));

    int cnt=0;//找到两个块之间连线的点 
    for(int i=l;i<=r;i++) if(p[i].x>=p[mid].x-d && p[i].x<=p[mid].x+d) tmp[++cnt]=i;

    sort(tmp+1,tmp+cnt+1,cmp2);
    for(int i=1;i<=cnt;i++)
        for(int j=i+1;j<=cnt;j++)
        {
            if(p[tmp[i]].f!=p[tmp[j]].f)
            {
                if(p[tmp[j]].y-p[tmp[i]].y>=d) break;
                else d=min(d,dis(p[tmp[i]],p[tmp[j]]));
            }
        }
    return d;       
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
            p[i].f=1;
        }
        for(int i=n+1;i<=n+n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
            p[i].f=2;
        }
        sort(p+1,p+n+n+1,cmp1);
        printf("%.3lf\n",get(1,n+n));
    }
    return 0;
}