题意
题目描述
给定平面上\(n\)个点,找出其中的一对点的距离,使得在这\(n\)个点的所有点对中,该距离为所有点对中最小的。
输入输出格式
输入格式:
第一行:\(n\);\(2\leq n\leq 200000\)
接下来\(n\)行:每行两个实数:\(x\ y\),表示一个点的行坐标和列坐标,中间用一个空格隔开。
输出格式:
仅一行,一个实数,表示最短距离,精确到小数点后面\(4\)位。
输入输出样例
输入样例#1:
3
1 1
1 2
2 2
输出样例#1:
1.0000
说明
\(0\leq x,y\leq 10^9\)
思路
利用分治的方法实现。我们先把所有点按照横坐标排序,然后查询每一个区间的最近点对距离。假设当前查询的是\([l,r]\)区间的最近点对距离,那么这个区间的答案就在\([l,mid]\)区间的最近点对距离、\([mid+1,r]\)区间的最近点对距离、靠近中间的分别在两个区间中的一些点之间的距离中产生,我们主要考虑第三部分答案如何统计。
首先通过分治,我们已经求出了左右两区间的最近点对距离\(min\),接下来找到\([l,r]\)区间内横坐标与\(mid\)的横坐标相差不超过\(min\)的点,并将这些点两两匹配求出最近距离。这样能保证答案的正确性,但是时间复杂度呢?据说这样子做的时间复杂度是\(O(n\log n)\)的,所以也不用担心超时的问题。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n;
struct Point
{
double x,y;
bool operator < (const Point &sjf){return x<sjf.x;}
}p[200005],q[200005];
double devide(int l,int r)
{
if(l==r) return DBL_MAX;
else if(l+1==r) return sqrt((p[l].x-p[r].x)*(p[l].x-p[r].x)+(p[l].y-p[r].y)*(p[l].y-p[r].y));
int mid=(l+r)>>1,cnt=0;
double d=min(devide(l,mid),devide(mid+1,r));
for(int i=l;i<=r;i++) if(fabs(p[i].x-p[mid].x)<=d) q[++cnt]=p[i];
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt&&fabs(q[i].x-q[j].x)<=d;j++)
d=min(d,sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y)));
return d;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+1,p+n+1);
printf("%.4f",devide(1,n));
return 0;
}