POJ - 3714 Raid(平面最近点对模板题，几何)

题目链接：点击查看

题目大意：给出两个含有n个点的集合，在两个集合中分别任选一点，使得这两个点之间的距离最小

题目分析：因为n给到了1e5，所以n*n的暴力肯定是不行了，直接从网上copy了个分治优化的模板，时间复杂度为nlogn，可以求出n个点中相距最近的两个点的距离，对于这个题目而言，我们将两个集合中的点分个类，在求距离的时候，若是同类的点，直接返回无穷大即可，这样同类的点肯定不可能是答案了

代码：

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
using namespace std;
    
typedef long long LL;
    
const int inf=0x3f3f3f3f;
    
const int N=2e5+100;

struct Point
{
    double x,y;
    bool flag;
}point[N];

int y_sort[N];

int cmpx(Point a,Point b)//按照x对这些点从小到大排序
{
    return a.x<b.x;
}

int cmpy(int a,int b)//对最近点算法中的y_sort数组排序
{
    return point[a].y<point[b].y;
}

double dis(Point a,Point b)
{
	if(a.flag!=b.flag)
    	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    return 1e20;
}
/*
    最近点对算法,在point[first]--point[last]个点中寻找一个最短距离
    使用该算法前先对这些点排序
    sort(point,point+n,cmpx);
*/
double findMin(int first, int last)
{
    if((last-first)==1)
        return dis(point[first],point[last]);
    else if(last-first==2)
    {
        double d1 = dis(point[first],point[first+1]);
        double d2 = dis(point[first],point[first+2]);
        double d3 = dis(point[first+1],point[first+2]);
        return min(min(d1,d2),d3);
    }
    //二分
    int mid = (first+last)/2;
    double min_dist = min(findMin(first,mid),findMin(mid+1,last));
    if(min_dist==0)
        return 0;
    int y_end = 0;
    for(int i=mid;point[mid].x-point[i].x<min_dist&&i>=first;i--)
        y_sort[y_end++]=i;
    for(int i=mid+1;point[i].x-point[mid+1].x<min_dist&&i<=last;i++)
        y_sort[y_end++]=i;
    sort(y_sort,y_sort+y_end,cmpy);
    for(int i=0;i<y_end;i++)
        for(int j=i+1;j<y_end&&(point[y_sort[j]].y-point[y_sort[i]].y)<min_dist;j++)
            min_dist=min(min_dist,dis(point[y_sort[i]],point[y_sort[j]]));
    return min_dist;
}
 
int main()
{
//  freopen("input.txt","r",stdin);
//  ios::sync_with_stdio(false);
	int w;
	cin>>w;
	while(w--)
	{
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%lf%lf",&point[i].x,&point[i].y);
			point[i].flag=true;
		}
		for(int i=n;i<2*n;i++)
		{
			scanf("%lf%lf",&point[i].x,&point[i].y);
			point[i].flag=false;
		}
		sort(point,point+2*n,cmpx);
		printf("%.3f\n",findMin(0,2*n-1));
	}
	
	
	 
	
	
	
	
	
	
        
        
        
        
         
        
    return 0;
}