POJ3714 Raid

题意

给出两组点，求两组点间的最近点对。

每个组中点数 $N\le 1000$ ，坐标 $x,y\le 10^9$ 。

题解

按 $x$ 坐标分治，并且对分别属于左右块的点对单独处理。注意数组需要开两倍。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct node {
    ll x,y,id;
} s[200005];
ll t,n;

inline bool cmp(const node &x,const node &y) { return x.x==y.x ? x.y<y.y : x.x<y.x; }

inline double dis(ll x1,ll y1,ll x2,ll y2) { return sqrt(1.0*((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); }

double work(ll l,ll r)
{
    if (l>=r) return 1e18;
    ll mid=(l+r)>>1;
    double ans=min(work(l,mid),work(mid+1,r));
    for (ll i=mid;i>=l;i--)
    {
        if (s[mid].x-s[i].x>=ans) break;
        for (ll j=mid+1;j<=r;j++)
        {
            if (s[j].x-s[i].x>=ans) break;
            if (s[i].id==s[j].id) continue;
            ans=min(ans,dis(s[i].x,s[i].y,s[j].x,s[j].y));
        }
    }
    return ans;
}

signed main()
{
    t=read();
    while (t--)
    {
        n=read();
        for (ll i=1;i<=n;i++) s[i].x=read(),s[i].y=read(),s[i].id=1;
        for (ll i=n+1;i<=(n<<1);i++) s[i].x=read(),s[i].y=read(),s[i].id=2;
        n<<=1;
        sort(s+1,s+n+1,cmp);
        printf("%.3f\n",work(1,n));
    }
    return 0;
}