【POJ 3714】Raid

【题目链接】:http://poj.org/problem?id=3714

【题意】

给你两类的点;
各n个;
然后让你求出2*n个点中的最近点对的距离;
这里的距离定义为不同类型的点之间的距离;

【题解】

分治法;
不断划分小区间;
求出小区间内的最小值;
为后面的大区间剪枝;
只是要求点的类型不同才能剪枝了;

【Number Of WA】

0

【完整代码】

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 2e5+100;
const LL oo = 5e18;

struct node{
    LL x,y;
    int p;
};

int n;
node a[N],b[N];

bool cmp1(node a,node b){
    return a.x < b.x;
}

bool cmp2(node a,node b){
    return a.y < b.y;
}

LL sqr(LL x){
    return x*x;
}

LL dis(node a,node b){
    LL temp = 0;
    temp+=sqr(a.x-b.x);
    temp+=sqr(a.y-b.y);
    return temp;
}

LL solve(int l,int r){
    LL ret = oo;
    if (l>=r) return ret;
    if (l+1==r) {
            if (a[l].p!=a[r].p)
                return dis(a[l],a[r]);
            else
                return ret;
    }
    int m = (l+r)>>1;
    LL ret1 = solve(l,m),ret2 = solve(m+1,r),temp;
    ret = min(ret1,ret2);
    int k = 0;
    rep2(i,m,l){
        temp =sqr(a[m].x-a[i].x);
        if (temp>ret && a[m].p != a[i].p) break;
        b[++k] = a[i];
    }
    rep1(i,m+1,r){
        temp = sqr(a[m].x-a[i].x);
        if (temp>ret && a[m].p != a[i].p) break;
        b[++k] = a[i];
    }
    sort(b+1,b+1+k,cmp2);
    rep1(i,1,k){
        rep1(j,i+1,k){
            if (b[i].p==b[j].p) continue;
            temp = sqr(b[i].y-b[j].y);
            if (temp > ret) break;
            temp = dis(b[i],b[j]);
            if (temp < ret) ret = temp;
        }
    }
    return ret;
}

int main(){
    //Open();
    Close();
    int T;
    cin >> T;
    while (T--){
        cin >> n;
        rep1(i,1,n){
            cin >> a[i].x >> a[i].y;
            a[i].p = 0;
        }
        rep1(i,n+1,2*n){
            cin >> a[i].x >> a[i].y;
            a[i].p = 1;
        }
        n<<=1;
        sort(a+1,a+1+n,cmp1);
        cout << fixed << setprecision(3) << double (sqrt(1.0*solve(1,n))) << endl;
    }
    return 0;
}