P7883 平面最近点对(加强加强版) 题解

题意

题目链接

给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$,请输出距离最近的两个点的距离。

解析

在这题下给一篇正经的分治做法,已有的分治做法是用 vector 实现的,可能对于部分同学来说代码实现不便。其他题解都是非分治的。

我们将所有点按照 $x$ 坐标排序后标号为 $1,2,\dots n$,记 $\operatorname{solve}(l,r)$ 为计算出 $[l,r]$ 内所有点的平面最近点对并返回其距离。考虑分治,记 $mid=\lfloor\frac{l+r}{2}\rfloor$,可以先进行 $\operatorname{solve}(l,mid)$ 和 $\operatorname{solve}(mid+1,r)$,考虑如何合并信息。

在记 $d$ 为 $\operatorname{solve}(l,mid)$ 和 $\operatorname{solve}(mid+1,r)$ 的较小值。容易发现我们仅需要考虑 $|x_i-x_{mid}|<d$ 的点($x_i$ 为点 $i$ 的横坐标)。我们找出这些点,并将其按 $y$ 坐标排序。

之后我们暴力依次遍历这些点,对于遍历到的每个点,再往后暴力遍历直至 $y_j-y_i \ge d$ 为止。由 $d$ 的定义可以知道位于同一侧的点的距离一定 $\ge d$,再结合画图可以知道,每个点往后暴力遍历至多遍历 $7$ 个点,因此合并操作的复杂度为 $O(n)$。结合分治和每次进行的对 $y$ 排序,最终复杂度为 $O(n\log^2 n)$。

事实上,分治本质与归并排序相同,因此可以在分治过程中对 $y$ 进行排序,复杂度可以优化至 $O(n\log n)$,不过本代码中并没有实现。

代码

#include<bits/stdc++.h>
#define pi pair<int,int>
#define x first
#define y second
#define ll long long
using namespace std;
const int N=4e5+5;
int n;
pi a[N],b[N];
inline double dis(pi i,pi j){
    return sqrt((ll)(i.x-j.x)*(i.x-j.x)+(ll)(i.y-j.y)*(i.y-j.y));
}//计算距离
inline bool cmp(pi i,pi j){
    return i.y<j.y;
}
inline double solve(int l,int r){
    if(l==r) return 1e9;
    int mid=(l+r)>>1;
    double d=1e9;
    d=min(solve(l,mid),solve(mid+1,r));//分治计算
    int cnt=0;
    for(int i=l;i<=r;i++){//取出有用的点
        if(fabs(a[mid].x-a[i].x)<d) b[++cnt]=a[i];
    }
    sort(b+1,b+1+cnt,cmp);//对 y 排序
    for(int i=1;i<=cnt;i++){//暴力合并
        for(int j=i+1;j<=cnt;j++){
            if(b[j].y-b[i].y>=d) break;
            d=min(d,dis(b[i],b[j]));
        }
    }
    return d;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a+1,a+1+n);//对 x 排序
    double ans=solve(1,n);
    printf("%.0lf\n",ans*ans);//最后输出平方
    return 0;
}
本文作者:water_tomato

评论

  1. Nelson
    2年前
    2021-11-02 21:35:52

    你好,你的题解写的非常详细!但是我按照你的写法写了但是超时了一大半,能否帮我看一下呢,谢谢!

    • 博主
      Nelson
      2年前
      2021-11-03 19:31:43

      你的 res 存的是距离的平方而不是距离,用 y 的差进行比较的时候肯定要和距离比较而不能和距离的平方比较,你的代码会导致 tmp[j].y-tmp[i].y>=res 很难执行,因为 res 是平方所以巨大。

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇