「Solution」平面最近点对

分治

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5; 
const double INF = 0x3f3f3f3f;
const double eps = 1e-7;

int t, n;
double ans;

struct node {
	int x, y, z;
} p[MAXN * 2];
bool cmp (node a, node b) {
	return a.x < b.x;
}

double dis (int a, int b) {
	if (p[a].z == p[b].z) return INF;
	return sqrt (double(p[a].x - p[b].x) * (p[a].x - p[b].x) + double(p[a].y - p[b].y) * (p[a].y - p[b].y)); //double 不能丢
}

double Dist (int l, int r) {
	if (l == r) return INF;
	if (r - l == 1) return dis (l, r);
	int mid = (l + r) >> 1;
	double tmp = min (Dist (l, mid), Dist (mid, r));
	for (int i = mid - 1; i >= l; i--) {
		if (p[mid].x - p[i].x + eps > tmp) break;
		for (int j = mid + 1; j <= r; j++) {
			if (p[j].x - p[i].x + eps > tmp) break;
			tmp = min (tmp, dis (i, j));
		}
	}
	return tmp;
}

int main () {
	scanf ("%d", &t);
	while (t--) {
		scanf ("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf ("%d %d", &p[i].x, &p[i].y);
			p[i].z = 0;
		}
		for (int i = 1; i <= n; i++) {
			scanf ("%d %d", &p[i + n].x, &p[i + n].y);
			p[i + n].z = 1;
		}
		sort (p + 1, p + 1 + 2 * n, cmp);
		printf ("%.3lf\n", Dist (1, 2 * n));
	}
	return 0;
}