https://www.acwing.com/problem/content/121/
给两种点,黑点和红点各n(n<=1e5)个,求最近的黑点和红点之间的距离,xy在1e9范围内。
随机旋转法。先sort一遍更新d使得d尽可能变小,然后randomshuffle(实际上貌似只需要randomshuffle其中一个就够了),再更新一边d使得d尽可能变小。
然后随机乱旋转一通,根据已经缩小的d找出可能更新答案的上下界(二分找出来),然后暴力更新,随着更新的过程进行d可能会进一步变小,复杂度不能保证但是感觉问题应该不会很大。何况是randomshuffle之后又随机乱转一通,什么精心构造的数据应该都完蛋了。
#include<bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
struct Point {
double x, y;
Point() {}
inline bool operator<(const Point &b) const {
return x < b.x;
}
} p[100000 + 5], q[100000 + 5], tmp;
int n;
inline double RandomDouble() {
return 1.0 * rand() / RAND_MAX;
}
inline bool cmp(const Point &a, const Point &b) {
return a.x < b.x;
}
inline double dis(const Point &a, const Point &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double Calc(const double &A, double d) {
double x0 = -1e9 + 2e9 * RandomDouble(), y0 = -1e9 + 2e9 * RandomDouble(); //随机弄一个旋转原点
double cosA = cos(A), sinA = sin(A);
double xc = -x0 * cosA + y0 * sinA + x0;
double yc = -x0 * sinA - y0 * cosA + y0;
//利用图形学的知识加速
for(int i = 1; i <= n; ++i) {
double x = p[i].x, y = p[i].y;
p[i].x = x * cosA - y * sinA + xc;
p[i].y = x * sinA + y * cosA + yc;
}
sort(p + 1, p + 1 + n);
for(int i = 1; i <= n; i++) {
double x = q[i].x, y = q[i].y;
q[i].x = x * cosA - y * sinA + xc;
q[i].y = x * sinA + y * cosA + yc;
}
sort(q + 1, q + 1 + n);
for(int i = 1; i <= n; ++i) {
tmp.x = p[i].x - d;
int minj = max(1, int(lower_bound(q + 1, q + 1 + n, tmp) - q));
tmp.x = p[i].x + d;
int maxj = min(n, int(lower_bound(q + 1, q + 1 + n, tmp) - q));
for(int j = minj; j <= maxj && q[j].x - p[i].x < d; j++)
d = min(d, dis(p[i], q[j]));
}
return d;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
srand(time(0));
int t;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%lf%lf", &p[i].x, &p[i].y);
for(int i = 1; i <= n; ++i)
scanf("%lf%lf", &q[i].x, &q[i].y);
double d = 1e36;
sort(p + 1, p + 1 + n);
sort(q + 1, q + 1 + n);
for(int i = 1; i <= n; ++i) {
int c = min(n, i + 5);
for(int j = max(1, i - 5); j <= c; ++j) {
d = min(d, dis(p[i], q[j]));
}
}
random_shuffle(p + 1, p + 1 + n);
random_shuffle(q + 1, q + 1 + n);
for(int i = 1; i <= n; ++i) {
int c = min(n, i + 5);
for(int j = max(1, i - 5); j <= c; ++j) {
d = min(d, dis(p[i], q[j]));
}
}
d = Calc(RandomDouble() * 2.0 * PI, d);
//d = Calc(RandomDouble() * 2.0 * PI, d);
//d = Calc(RandomDouble() * 2.0 * PI, d);
printf("%.3f\n", d);
}
return 0;
}