平面上的最接近點對

2020 年 12 月 7 日
筆記
洛谷

題目描述

給定平面上

輸入格式

第一行一個整數

接下來

輸出格式

僅一行，一個實數，表示最短距離，四捨五入保留

輸入輸出樣例

輸入

輸出

1.0000

說明/提示

數據規模與約定

對於 $100\%100% 的數據，保證 1 ≤ n ≤ 10^41≤n≤104，0 ≤ x, y ≤ 10^9，0≤x,y≤109，小數點後的數字個數不超過 66。$

分治法求解

分解

對所有的點按照

解決

遞歸的尋找兩個集合中的最近點對。取兩個集合最近點對中的最小值 $min(dis_{left},dis_{right})min(disleft,disright)$

合併

最近距離不一定存在於兩個集合中，可能一個點在集合 $dis=min(dis_{left},dis_{right}) 。那麼一個點在集合 A，一個在集合 B中的情況，可以針對此情況，用之前分解的標準值，即按照 x 坐標(或者 y)從小到大排序後的中間點的 x 坐標作為 mid。劃分一個 [mid-dis,mid+dis] 區域，如果存在最小距離點對，必定存在這個區域中。<img alt="" src="//cdn.luogu.com.cn/upload/pic/60270.png" style=""/> 之後只需要根據左邊區域 [mid-dis,mid][mid−dis,mid] 的點來遍歷右邊區域 [mid,mid+dis][mid,mid+dis] 的點，即可找到是否存在小於 disdis 距離的點對。但是存在一個最壞情況，即通過左右兩個區域計算得到的 disdis 距離來劃分的第三區域可能包含集合所有的點，這時候進行遍歷查找，時間複雜度仍然和 brute forcebruteforce 方法相同，都為O(n^2)O(n2)。因此需要對此進行深一步的考慮。$

1985年 Preparata 和 Shamos 在給出該問題的一個分治算法並且還具體分析了在

此結論很好證明，通過在 $δ$

用反證法來證明，假設存在大於6個點，則必有一個或多個小長方形存在兩個及以上點，而小長方形的最長距離是為對角線長度，為：

時間複雜度

在分解和合併時，可能存在按照x軸、y軸進行排序的預處理O(nlogn)，該問題在解決階段只做提取的操作為Θ(n)，遞推式為：

計算後得到整體時間複雜度為:

代碼

#include<bits/stdc++.h>
using namespace std;
struct point
{
    double x,y;
}p[200010];
int n,temp[200010];
bool cmp(const point &A,const point &B)
{
    if(A.x==B.x)
        return A.y<B.y;
    else
        return A.x<B.x;
}
bool cmps(const int &a,const int &b)
{
    return p[a].y<p[b].y;
}
double distance(int i,int j)
{
    return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
}
double merge(int left,int right)
{
    double dis=2<<20;
    if(left==right)
        return dis;
    if(left+1==right)
        return distance(left,right);
    int mid=(left+right)>>1;
    double d1=merge(left,mid);
    double d2=merge(mid+1,right);
    dis=min(d1,d2);
    int k=0;
    for(int i=left;i<=right;i++)
        if(fabs(p[i].x-p[mid].x)<=dis)
            temp[k++]=i;
    sort(temp,temp+k,cmps);
    for(int i=0;i<k;i++)
        for(int j=i+1;j<k&&p[temp[j]].y-p[temp[i]].y<dis;j++)
            dis=min(dis,distance(temp[i],temp[j]));
    return dis; 
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%lf %lf",&p[i].x,&p[i].y);
    sort(p,p+n,cmp);
    printf("%.4lf\n",merge(0,n-1));
    return 0;
}

不用分治

#include <bits/stdc++.h>
using namespace std;
struct point{
    double x,y;
}p[100001];
double dist(point a,point b){
    return sqrt(pow(fabs(a.x-b.x),2)+pow(fabs(a.y-b.y),2));
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
    }
    double mindist=dist(p[1],p[2]);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(dist(p[i],p[j])<mindist)
            mindist=dist(p[i],p[j]);
        }
　　}
　　cout<<fixed<<setprecision(4)<<mindist;
    return 0;
}

Tags: 洛谷