分治 平面上的最近点对

字数统计913阅读时长7分阅读次数

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

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

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

输入输出样例
输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
2
3
1.0000
1.4142
1.4142

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

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

  1. 最短距离两点都在同一侧：
    对于这种来说递归的终止时只需计算2-3点的距离，设计这两种情况的递归终止条件即可。
  2. 最短距离两点分别在两侧：
    1. 由于我们先递归求得左右两侧的最短距离minDistance1和minDistance2
    2. 求出左右两侧的较短距离minDistance = min{minDistance1,minDistance2};
    3. 现在只需要比距离d小的点，这时我们以中间的坐标x为准，对[x-d,x+d]之间的点暴力进行判断，找出最小值就可以得到答案了

在这里插入图片描述

代码详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}

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