POJ 3714 Raid(分治)

题目：3714

题意：有两个点集，求两个点集任意两点最小的距离

题解：

1. 将两个点集合并，采用分治法求平面点集距离
2. 优化：分治左右两边求 mid-d  -----  mid+d 之间的点，节省时间

AC代码：

#include<iostream>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;

typedef long long LL;
#define MAXN 100010
#define INF 100000000000
int T;
int n;
double ans;

struct Node {
	LL x;
	LL y;
	int id;
	Node(LL x = 0, LL y = 0, int id = 0):x(x),y(y),id(id){}
	bool operator < (Node node) {
		return x == node.x ? y < node.y : x < node.x;
	}
}no[MAXN * 2];

double dis(Node a, Node b) {  //求两点之间的距离
	return sqrt((double)((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)));
}

double solve(int l, int r) {  //分治
	if (l == r)return INF;
	int mid = (l + r) >> 1;
	double dl = solve(l, mid);
	double dr = solve(mid + 1, r);
	double d = min(dl, dr);
	for (int i = mid; i >= l; i--) {
		if ((no[mid].x - no[i].x) > d)break;
		for (int j = mid + 1; j <= r; j++) {
			if ((no[j].x - no[mid].x) > d)break;
			double temp = dis(no[i], no[j]);
			if (no[i].id != no[j].id && temp < d)d = temp;
		}
	}
	return d;

}
int main() {
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> no[i].x >> no[i].y;
			no[i].id = 0;
		}
		for (int i = 0; i < n; i++) {
			cin >> no[i + n].x >> no[i + n].y;
			no[i + n].id = 1;
		}
		sort(no, no + 2 * n);
		ans = solve(0, 2 * n - 1);
		cout << setiosflags(ios::fixed) << setprecision(3) << ans << endl;
	}
	return 0;
}