POJ3714 Raid 分治/K-D Tree

时间：2022-09-06 23:59:15

VJ传送门

简要题意：给出两个大小均为\(N\)的点集\(A,B\)，试在\(A\)中选择一个点，在\(B\)中选择一个点，使得它们在所有可能的选择方案中欧几里得距离最小，求出这个距离

下面给出的两种解法基本上都能够被卡成\(O(n^2)\)……

①

按照平面最近点对的做法去做，只是在贡献答案的时候加上所属点集不同的限制就可以了。

当然这个可以卡，只要把\(A\)、\(B\)集合之间分得很开，而\(A\)集合和\(B\)集合内部的点两两之间的距离很小，这样在分治下去的过程中没法贡献答案，最后在分治的第一层就有可能会退化成\(O(n^2)\)

如果你愿意可以旋转坐标系来部分解决上面的问题

代码没有写

②

K-D Tree

把\(A\)集合的点全部加进去构建K-D Tree，对于\(B\)集合内的每个点在K-D Tree上搜索，加个最优化剪枝。

这个怎么卡应该不需要说了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
#define ld long double
#define int long long
//This code is written by Itst
using namespace std;

inline int read(){
    int a = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c) && c != EOF){
        if(c == '-')
            f = 1;
        c = getchar();
    }
    if(c == EOF)
        exit(0);
    while(isdigit(c)){
        a = a * 10 + c - 48;
        c = getchar();
    }
    return f ? -a : a;
}

const int MAXN = 1e5 + 7;
struct point{
    int x , y , ind;
    point(int _x = 0 , int _y = 0 , int _i = 0):x(_x) , y(_y) , ind(_i){}
}P[MAXN];
int N , rt;
int ch[MAXN][2] , X[MAXN][2] , Y[MAXN][2] , p[MAXN][2];
ld ans;

bool cmp1(point a , point b){
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

bool cmp2(point a , point b){
    return a.y == b.y ? a.x < b.x : a.y < b.y;
}

inline ld calc(point a , point b){
    return sqrt((long double)(a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

inline void merge(int x , int y){
    X[x][0] = min(X[x][0] , X[y][0]);
    X[x][1] = max(X[x][1] , X[y][1]);
    Y[x][0] = min(Y[x][0] , Y[y][0]);
    Y[x][1] = max(Y[x][1] , Y[y][1]);
}

int build(int l , int r , bool f){
    if(l > r)
        return 0;
    int mid = (l + r) >> 1;
    nth_element(P + l , P + mid , P + r + 1 , f ? cmp1 : cmp2);
    int t = P[mid].ind;
    X[t][0] = X[t][1] = P[mid].x;
    Y[t][0] = Y[t][1] = P[mid].y;
    if(ch[t][0] = build(l , mid - 1 , f ^ 1))
        merge(t , ch[t][0]);
    if(ch[t][1] = build(mid + 1 , r , f ^ 1))
        merge(t , ch[t][1]);
    return t;
}

inline ld qw(int x , point p){
    int mx = max(max(X[x][0] - p.x , p.x - X[x][1]) , 0ll) , my = max(max(Y[x][0] - p.y , p.y - Y[x][1]) , 0ll);
    return sqrt((long double)mx * mx + my * my);
}

void dfs(int x , point q , bool f){
    if(x == 0 || qw(x , q) > ans)
        return;
    ans = min(ans , calc(point(p[x][0] , p[x][1]) , q));
    if(f ? cmp1(point(p[x][0] , p[x][1]) , q) : cmp2(point(p[x][0] , p[x][1]) , q)){
        dfs(ch[x][1] , q , f ^ 1);
        dfs(ch[x][0] , q , f ^ 1);
    }
    else{
        dfs(ch[x][0] , q , f ^ 1);
        dfs(ch[x][1] , q , f ^ 1);
    }
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    for(int T = read() ; T ; --T){
        N = read();
        for(int i = 1 ; i <= N ; ++i){
            P[i].x = p[i][0] = read();
            P[i].y = p[i][1] = read();
            P[i].ind = i;
        }
        rt = build(1 , N , 0);
        ans = 1e50;
        for(int i = 1 ; i <= N ; ++i){
            P[0].x = read();
            P[0].y = read();
            dfs(rt , P[0] , 0);
        }
        cout << fixed << setprecision(3) << ans << endl;
    }
    return 0;
}

相关文章