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

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;
}

 

相关标签: 分治