poj3714 Raid（分治求平面最近点对）

题目链接：https://vjudge.net/problem/POJ-3714

题意：给定两个点集，求最短距离。

思路：在平面最近点对基础上加了个条件，我么不访用f做标记，集合1的f为1，集合2的f为-1，那么求两个点的距离时，如果a.f*b.f=-1时计算距离，否则乘积为1的话返回inf。其它就和hdoj1007一样了.

AC代码：

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstdlib>

using namespace std;

const int maxn=2e5+;

const double inf=1e30;

int T,n,cnt,id[maxn];

struct node{

    int x,y,f;

}pt[maxn];

bool operator < (const node& a,const node& b){

    if(a.x==b.x) return a.y<b.y;

    return a.x<b.x;

}

bool cmp(int a,int b){

    return pt[a].y<pt[b].y;

}

double dist(const node& a,const node& b){

    if(a.f*b.f==) return inf;

    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));

}

double fenzhi(int l,int r){

    double d=inf;

    if(l==r) return d;

    if(l+==r) return dist(pt[l],pt[r]);

    int mid=(l+r)>>;

    d=min(fenzhi(l,mid),fenzhi(mid+,r));

    cnt=;

    int t1,t2,l1=l,r1=mid,mid1;

    while(l1<=r1){

        mid1=(l1+r1)>>;

        if(pt[mid].x-pt[mid1].x<d) r1=mid1-;

        else l1=mid1+;

    }

    t1=l1;

    l1=mid+,r1=r;

    while(l1<=r1){

        mid1=(l1+r1)>>;

        if(pt[mid1].x-pt[mid].x<d) l1=mid1+;

        else r1=mid1-;

    }

    t2=r1;

    for(int i=t1;i<=t2;++i)

            id[++cnt]=i;

    sort(id+,id+cnt+,cmp);

    for(int i=;i<cnt;++i)

        for(int j=i+;j<=cnt&&(pt[id[j]].y-pt[id[i]].y<d);++j)

            d=min(d,dist(pt[id[i]],pt[id[j]]));

    return d;

}

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        for(int i=;i<=*n;++i){

            scanf("%d%d",&pt[i].x,&pt[i].y);

            if(i<=n) pt[i].f=;

            else pt[i].f=-;

        }

        sort(pt+,pt++*n);

        printf("%.3f\n",fenzhi(,*n));

    }

    return ;

}