POJ3714 Raid

题目链接

题目链接

题意

给两组数目相同的点，求任意两个不同组的点的最短距离

思路

• 分治，把每次把点按x一分为二，求最短的距离，注意对于跨越分割线的点的连线需要特别判断
• 数据很大，会爆int
• printf()没有对于%lf的定义,要使用%f

参考代码

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;
double maxa=1e50;
struct node
{
    double x,y;
    int kind;
};
node aa[200100];
node tmp[201000];
bool cmpx(node a,node b)
{
    return a.x<b.x;
}
bool cmpy(node a,node b)
{
    return a.y<b.y;
}
double dis(node a,node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double js(int l,int r)
{
    if(l==r)
        return maxa;
    int mid = (l+r)/2;
    double re=min(js(l,mid),js(mid+1,r));
    int s=0;
    for(int i=l; i<=r; i++)
    {
        if(fabs(aa[i].x-aa[mid].x)<=re)
        {
            tmp[s++]=aa[i];
        }
    }
    sort(tmp,tmp+s,cmpy);
    for(int i=0; i<s; i++)
    {
        for(int j=i+1; j<s; j++)
        {
            if(tmp[j].y-tmp[i].y>re)
                break;
            if(tmp[i].kind!=tmp[j].kind)
            {
                re=min(re,dis(tmp[i],tmp[j]));
            }
        }
    }
    return re;
 
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        double ans=0;
        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf",&aa[i].x,&aa[i].y);
            aa[i].kind=0;
        }
        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf",&aa[i+n].x,&aa[i+n].y);
            aa[i+n].kind=1;
        }
        sort(aa,aa+2*n,cmpx);
        ans=js(0,2*n-1);
        printf("%.3f\n",ans);
    }
}