该题就是距离平面对点最小的变种
下面代码带注释
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N = 200010; const long long INF = 1e10; struct Point { double x, y; bool type; bool operator < ( const Point & w) const { return x < w.x; } }points[N],temp[N];//归并辅助数组 double dirt(Point a, Point b) { //如果它们的派别是相同的就返回正无穷 if(a.type == b.type) return INF; double dx = a.x - b.x, dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } double dfs(int l,int r) { if(l >= r) return INF; int mid = l + r >> 1; double mid_x = points[mid].x;//首先记录划分线 double res = min(dfs(l,mid),dfs(mid + 1,r)); //作用块 {//归并排序 i 是左半边的指针 j 是右半边的指针 // 将l 到 r 中的点按 y 的大小排序 int k = 0, i = l, j = mid + 1; while(i <= mid && j <= r) if(points[i].y <= points[j].y) temp[k ++] = points[i ++]; //结构体一一对应赋值 else temp[k ++] = points[j ++]; while(j <= r) temp[k ++] = points[j ++]; while(i <= mid) temp[k ++] = points[i ++]; for(i = 0,j = l; i < k; i ++,j ++) points[j] = temp[i]; } //从左右两边递归出来的结果 //因为直线距离大过res可以排除 int k = 0;//取出在划分线左右的点 //取出res范为内的点 for(int i = l; i <= r; ++ i) if(points[i].x >= mid_x - res && points[i].x <= mid_x + res) temp[k ++] = points[i]; //此时已经按照y的大小排好序 for(int i = 0; i < k; ++ i) for(int j = i - 1; j >= 0 && temp[i].y - temp[j].y <= res; j --) res = min(res,dirt(temp[i],temp[j])); return res; } int main() { int T, n; cin >> T; while (T --) {//读入排序 cin >> n; //前n个数是红方 for(int i = 0; i < n; ++ i) { cin >> points[i].x >> points[i].y; points[i].type = 0; } for(int i = n; i < n * 2; ++ i) { cin >> points[i].x >> points[i].y; points[i].type = 1; } sort(points,points + n * 2);//按横坐标排序 printf("%.3f\n",dfs(0,n * 2 - 1));//开始分治 } return 0; }