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

poj 3714 - 平面最近点对

程序员文章站 2022-03-30 08:39:23
...

题目链接:点击这里

 

解题思路:

在原有的分治算法上加上标记,如果标记不同的则计算距离,不然的话就返回无穷大.

用归并排序再可以省下logn

这题要是卡数据不知道有什么更高深的办法.

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int mx = 2e5 + 10;
const double INF = 1.0*1e30;
int n,m;
struct node
{
	double x,y;
	bool f;
	bool operator < (node A)const
	{
		return x < A.x;
	}
}s[mx],kep[mx];
double dist(node A,node	B)
{
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double divide(int l,int r)
{
	if(l==r) return INF;
	int mid = (l+r)>>1,tot = 0;
	double X = s[mid].x;
	double d = min(divide(l,mid),divide(mid+1,r)); 
	for(int i=l,j=mid+1;i<=mid;i++){
		while(j<=r&&s[j].y<=s[i].y) kep[tot++] = s[j++];
		kep[tot++] = s[i];
	}
	for(int i=0;i<tot;i++) s[i+l] = kep[i];
	tot = 0;
	for(int i=l;i<=r;i++){
		if(fabs(s[i].x-X)<d)
		kep[tot++] = s[i];
	}
	for(int i=0;i<tot;i++){
		for(int j=i+1;j<tot;j++){
			if(kep[j].y-kep[i].y>d) break;
			if(kep[j].f!=kep[i].f)
			d = min(d,dist(kep[i],kep[j]));
		}
	}
	return d;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%lf%lf",&s[i].x,&s[i].y),s[i].f = 0;
		for(int i=n+1;i<=2*n;i++) scanf("%lf%lf",&s[i].x,&s[i].y),s[i].f = 1;
		sort(s+1,s+1+2*n);
		printf("%.3f\n",divide(1,2*n));	
	}
	return 0;
}