P1429 平面最近点对(加强版)
程序员文章站
2022-03-03 08:24:47
...
题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的
输入格式
第一行:n;2≤n≤200000
接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。
输出格式
仅一行,一个实数,表示最短距离,精确到小数点后面4位。
输入输出样例
输入 #1复制
3 1 1 1 2 2 2
输出 #1复制
1.0000
说明/提示
0<=x,y<=10^9
思路:分治法
设n个点组成集合S([L,R]),将集合分成基本均等的两个集合s1(L,M),s2(M+1,R),分别求出两个集合内部两点间的最小值,为d1,d2, d=min(d1,d2);
最佳方案的取值来源于:
都是集合1 d1
都是集合2 d2
横跨集合1,2
关键在求第三种情况,那么只要取在中间地带,在[L,R]所有点去寻找跟M点的横坐标距离比d还要小的点,最后暴力遍历取最值即可。
#include <bits/stdc++.h>
using namespace std;
struct node{
double x,y;
};
double dis(node n1, node n2){
return sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));
}
bool cmp(const node &a, const node &b){//按照横坐标排序
return a.x<b.x;
}
node a[200005],b[200005];
double fun(int l, int r){
if(l==r) return 9999999999.0000;
int mid=(l+r)>>1;
double x=min(fun(l, mid),fun(mid+1,r));//分
int k=0;
for(int i=l; i<=r; i++){
if(fabs(a[i].x-a[mid].x)<x){//得到可能是最佳方案的点
b[++k]=a[i];
}
}
for(int i=1; i<k; i++){//暴力搜一遍
for(int j=i+1; j<=k; j++){
x=min(dis(b[i],b[j]),x);//合
}
}
return x;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n; i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+1+n,cmp);
cout<<fixed<<setprecision(4)<<fun(1,n)<<endl;
return 0;
}