VJ傳送門
簡要題意：給出兩個大小均為\(N\)的點集\(A,B\)，試在\(A\)中選擇一個點，在\(B\)中選擇一個點，使得它們在所有可能的選擇方案中歐幾里得距離最小，求出這個距離
下面給出的兩種解法基本上都能夠被卡成\(O(n^2)\)……
①
poj1741，按照平面最近點對的做法去做，只是在貢獻答案的時候加上所屬點集不同的限制就可以了。
當然這個可以卡，只要把\(A\)、\(B\)集合之間分得很開，而\(A\)集合和\(B\)集合內部的點兩兩之間的距離很小，這樣在分治下去的過程中沒法貢獻答案，最后在分治的第一層就有可能會退化成\(O(n^2)\)
如果你愿意可以旋轉坐標系來部分解決上面的問題
代碼沒有寫
②
poj2352，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_JUDGEfreopen("in","r",stdin);freopen("out","w",stdout);
#endiffor(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;
}
