欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 3714 Raid 分治法求最近对问题

程序员文章站 2022-05-09 10:06:47
...

题目链接:POJ3714

解析:本题是分治法求最近对问题的应用。唯一变化的是标识flag,如果两个点是同一种类型,那么他们不能链接,就设为inf(无穷大)。其中sqrt()算法耗时很多,尽量可以先用不开根的结果运算,最后再开根,本题我没有这样做。

代码示例:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int inf = 10e8;
const int N = 100010;
struct Point{
	double x,y;
	bool flag;
}sa[2*N];//存放station和agent数据,其中flag来区别俩种类别 
int tmp[2*N];//用来记录以mid为中点,2d为宽度的点的下标  
bool cmpx(Point a,Point b){
	return a.x < b.x; 
}
bool cmpy(int a,int b){
	return sa[a].y < sa[b].y;
}

double dis(Point a,Point b){
	if(a.flag == b.flag)	return inf;
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
} 
double closest_pair(int l,int r){
	if(l == r)	return inf;
	if(l+1 == r)	return dis(sa[l],sa[r]);//只有俩个点,这俩个点的距离就是d 
	int mid = l + (r-l)/2;
	double d = min(closest_pair(l,mid),closest_pair(mid+1,r));//求出左右子区间最小的d 
	int cnt = 0;//用来记录以mid为中点,2d为宽度的点的下标 
	for(int i = l;i <= r;i++){
		if(abs(sa[mid].x - sa[i].x) <= d)	tmp[cnt++] = i;
	}
	sort(tmp,tmp+cnt,cmpy);//sort的应用,只对以tmp里元素为下标的sa结构体进行排序 
	for(int i = 0;i < cnt;i++)
		for(int j = i+1;j < cnt && sa[tmp[j]].y-sa[tmp[i]].y < d;j++){// 在d距离内才有可能有更小值 
			double d3 = dis(sa[tmp[i]],sa[tmp[j]]);
			if(d3 < d)	d = d3;
		}
	return d;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i = 0;i < n;i++)
			scanf("%lf %lf",&sa[i].x,&sa[i].y),sa[i].flag = true;
		for(int i = 0;i < n;i++)
			scanf("%lf %lf",&sa[i+n].x,&sa[i+n].y),sa[i+n].flag = false;
		sort(sa,sa+2*n,cmpx);
		printf("%.3f\n",closest_pair(0,2*n-1));
	}
	return 0;
}