蒟蒻的第一次题解

该题就是距离平面对点最小的变种
下面代码带注释

#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;
}