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

分治 平面上的最近点对

程序员文章站 2022-07-03 12:28:48
...

分治 平面上的最近点对
题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的。

输入格式:
多行输入
第一行:n;2≤n≤200000
接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式:
仅一行,一个实数,表示最短距离,精确到小数点后面4位。

输入输出样例
输入样例#1:

10
1 1
1 5
3 1
5 1
5 6
6 7
7 3
8 1
10 3
9 9
3
1 1
1 2
2 2
2
1 1
2 2

输出样例#1:

1.0000
1.4142
1.4142

说明
0<=x,y<=10^9

题目分析
先把点坐标x从小到大排序,然后从中间分开,最短距离有以下两种情况:

  1. 最短距离两点都在同一侧:
    对于这种来说递归的终止时只需计算2-3点的距离,设计这两种情况的递归终止条件即可。
  2. 最短距离两点分别在两侧:
    假设已知左边最短距离为d1,右边最短距离为d2,而这两部分最短距离d=min(d1,d2),但如果两点分别在左右半区的情况没有考虑,现在只需要比距离d小的点,这时我们以中间的坐标x0为准,对[x0-d,x0+d]之间的点进行查找,这时需要查找的点数量大大减少(排除多数点都集中在中间的情况,那就难搞了…),我们就可以用循环来枚举该区间内所有的点距离,并比较其最短距离是否比之前的d要小。
    分治 平面上的最近点对

代码详解

#include<bits/stdc++.h>
using namespace std;
struct node{//定义每个坐标
	double x,y;
}a[200010];
int c[200010];
double cmpy(int t1,int t2)  
{  
  return a[t1].y<a[t2].y;  
}  
bool cmp(node t1,node t2)
{
	return t1.x<t2.x;
}
double dis(node t1,node t2)//计算两点间的距离
{
	return sqrt((t1.x-t2.x)*(t1.x-t2.x)+(t1.y-t2.y)*(t1.y-t2.y));
}
double min(double t1,double t2)//返回较小数值
{
	return t1<t2?t1:t2;
}
double find(int left,int right)
{
	if(left+1==right)//如果只有两个点,则直接返回两点距离
		return dis(a[left],a[right]);
	if(left+2==right)//如果只有三个点,则求这三个点相距的最小距离
		return min(dis(a[left],a[right]),min(dis(a[left],a[left+1]),dis(a[left+1],a[right])));
	int mid=(left+right)>>1;//求中点
	double ans=min(find(left,mid),find(mid+1,right));  //将平面一分为二
    int i,j,cnt=0;  
    //------------------------核心代码-------------
    //有可能最小值的点位于分界直线两边,计算位于分界直线两边的点
    for(i=left;i<=right;i++)//将点坐标 x 到中间点坐标 a[mid] 的距离小于ans的值保存进数组c
		if(abs(a[mid].x-a[i].x)<ans)  
			c[cnt++]=i;  
	sort(c,c+cnt,cmpy);//将点坐标按 y 从小到大排序 
    for(i=0;i<cnt;i++) //比较数组c内两点距离找最小值(暴力,因为此时数据范围很小)
		for(j=i+1;j<cnt;j++)  
		{  
            //y坐标升序排列,有j>i所以差值肯定为正,故不需要绝对值
			if(a[c[j]].y-a[c[i]].y>ans)//如果y相差已经大于ans,则算上x肯定大于ans
				break;  
			ans=min(ans,dis(a[c[i]],a[c[j]]));//求出最小值了
		}
    return ans;
}
int main()
{
	int n,i;
    ios::sync_with_stdio(false);
    cin.tie(0);
	while(cin>>n)
	{
		for(i=0;i<n;i++)
			cin>>a[i].x>>a[i].y;
		std::sort(a,a+n,cmp);
		printf("%.4lf\n",find(0,n-1));
	}
	return 0;
}

代码思路,编辑格式不易,大家觉得还可以可以点赞收藏关注一下吧!