POJ3714 Raid——平面最近点对问题

题目链接

文章目录

题意：

给定两个集合A,B，各自包含某些点，在A种选取一个点 ( x a , y a ) (x_a,y_a) (xa​,ya​)，在B中选取一个点 ( x b , y b ) (x_b,y_b) (xb​,yb​)，求min(ab)。

思路

分治法求平面最近点对问题的改编，如果两个点属于同一集合，那么返回INF。
不懂平面最近点对问题的伙伴可以看看这篇博客
平面最近点对问题解释

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define mem(a,b) memset(a,b,sizeof a)
#define sd second
#define endl '\n'
#define N 200009
#define INF 1e20
using namespace std;
struct Point
{
	int x,y;
	int z;
}p[N];
int tmp[N];
bool cmp1(const Point & a,const Point &b)
{
	if(a.x!=b.x) return a.x<b.x;
	else return a.y<b.y;
}
bool cmpy(const int &a,const int &b)
{
	 return p[a].y<p[b].y;
}
double dis(int i,int j)
{
	if(p[i].z==p[j].z) return INF;
	return sqrt(1.0*(p[i].x-p[j].x)*(p[i].x-p[j].x)
	+1.0*(p[i].y-p[j].y)*(p[i].y-p[j].y));
}
double solve(int l,int r)
{
	if(l==r) return INF;
	if(r-l==1) return dis(l,r);
	int mid=(l+r)>>1;
	double lm=solve(l,mid);
	double rm=solve(mid+1,r);
	double mi=min(lm,rm);
//	cout<<mi<<endl;
	int t=0;
	for(int i=l; i<=r; i++)
	{
		if(1.0*abs(p[i].x-p[mid].x)<=mi) tmp[t++]=i;
	}
	sort(tmp,tmp+t,cmpy);
	for(int i=0; i<t; i++)
	{
		for(int j=i+1; j<t; j++)
		{
			if(1.0*abs(p[tmp[j]].y-p[tmp[i]].y)>=mi) break;
			if(p[tmp[i]].z!=p[tmp[j]].z) mi=min(mi,dis(tmp[i],tmp[j]));
		}
	}
	return mi;
}
int main()
{
	
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=0; i<2*n; i++)
		{
			scanf("%d%d",&p[i].x, &p[i].y);
			if(i<n) p[i].z=1;
			else p[i].z=2;
		}
		sort(p,p+2*n,cmp1);
		printf("%.3f\n",solve(0,2*n-1));
	}
	return 0;
 }