Raid 【POJ 3714】【分治求最近点对】

题目链接

题目大意

有两个集合，集合点都是n个，求两个集合中最近的点对是多少

解题思路

就是分治求最近点对的板子题；
用id标一下是哪个集合的点，只有分别是连个集合的才能求最近距离，不然就是inf
不知道为啥，这个题用vector超时了，最后用的结构体（QAQ）

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;

const int N=2e5+5;
struct node
{
    long long x,y;
    int id;
    node() {}
    node (long long X,long long Y,int ID)
    {
        x=X;
        y=Y;
        id=ID;
    }
};
node e[N*2],k[N*2];
int n;
long long inf=1000000000;

int cmpx(node a,node b)
{
    return a.x<b.x;
}

int cmpy(node a,node b)
{
    return a.y<b.y;
}

double dis(node a,node b)
{
    return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}

double half(int l,int r)
{
    if(l==r)
        return inf;
    else
    {
        int mid=(l+r)/2;
        double ans1=half(l,mid);
        double ans2=half(mid+1,r);
        double ans=min(ans1,ans2);
        int cnt=0;
        for(int i=l; i<=r; i++)
        {
            if(e[i].x>=e[mid].x-ans&&e[i].x<=e[mid].x+ans)
               k[cnt++]=e[i];
        }
        sort(k,k+cnt,cmpy);
        for(int i=0; i<cnt; i++)
        {
            for(int j=i+1; j<cnt; j++)
            {
                if((k[j].y-k[i].y)>ans)
                    break;
                else
                {
                    if(k[i].id!=k[j].id)
                    ans=min(dis(k[i],k[j]),ans);
                }
            }
        }
        return ans;
    }
}

int main()
{
    int T;
    long long x,y;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld %lld",&x,&y);
            e[i]=node(x,y,1);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%lld %lld",&x,&y);
            e[i+n]=node(x,y,2);
        }
        sort(e+1,e+1+n*2,cmpx);
        printf("%.3f\n",half(1,2*n));
    }
    return 0;
}