862 字
4 分钟
平面最近点对

问题#

给定平面上任意n个点,求最近的一对点之间的距离

思路#

我们使用类似于归并排序的思想解决这道题目.归并排序的思想是,如果一个区间的答案能够由二分划出的左区间,右区间,同时能够通过常数复杂度得到跨越mid左右区间的元素组成的答案,那么我们就可以以O(nlog(n))O(nlog(n))的复杂度解决这道题目. 容易想到,我们可以对x坐标进行排序,然后每次递归处理左右两个区间并取答案最小值. 所以问题就是,我们如何通过常数复杂度得到跨越mid的答案? 我们可以先做一些剪枝操作:

  1. 如果横坐标距离mid的x坐标大于等于已经得出的当前最小d,可以之间不参与计算
  2. 如果两个点的y坐标之差大于等于d,当前点以及比这个点y坐标大的点都不可以参与计算. 然后这次暴力枚举跨越左右区间答案的过程就神奇的变成了常数*n复杂度喵! 接下来给出证明: Pasted image 20260126164803 我们假设以及对y排好序,我们要找所有和当前点b距离最小的点,经过剪枝之后,我们实际上把当前点和所有可以匹配的点限制在了(2*d)*d的一个矩形区域内,即8个边长为d2\frac{d}{2}的小正方形,这个小正方形的对角线为2d2\frac{\sqrt{2}d}{2},小于d,但是当前两个点之间的距离最小是d,故一个小正方形内不可能有两个以上点,一次一个点最多只会和7个点参与计算.

CSES Minimum Euclidean Distance P1429 平面最近点对(加强版)

#include <algorithm>
#include <bits/stdc++.h>
#define N 1000005
#define pr pair<ll, ll>
#define ll __int128
using namespace std;
long long n, m, ans, x;
const ll mod = 1e9 + 7;
class Point {
public:
ll x = 0, y = 0;
ll operator*(const Point &oth) const { return x * oth.x + y * oth.y; }
ll mul(const Point &oth) const { return x * oth.y - y * oth.x; }
Point operator+(const Point &oth) const { return {x + oth.x, y + oth.y}; }
Point operator-(const Point &oth) { return {x - oth.x, y - oth.y}; }
ll dis(const Point &oth) { return (x - oth.x) * (x - oth.x) + (y - oth.y) * (y - oth.y); }
bool operator<(const Point &oth) { return make_pair(x, y) < make_pair(oth.x, oth.y); }
};
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
vector<Point> s(n + 5);
for (int i = 1; i <= n; i++) {
long long x, y;
cin >> x >> y;
s[i] = {x, y};
}
auto abs = [](ll x) { return x < 0 ? -x : x; };
sort(s.begin() + 1, s.begin() + n + 1);
auto merge_sort = [&](auto &&self, int l, int r) -> ll {
if (l == r)
return 1e19;
int mid = (l + r) >> 1;
ll M = s[mid].x; // 一定要记录中点 不然排序后就不是原来的中点了
ll d = min(self(self, l, mid), self(self, mid + 1, r));
inplace_merge(s.begin() + l, s.begin() + mid + 1, s.begin() + 1 + r,
[](const Point &a, const Point &b) { return a.y < b.y; });
vector<int> tem;
for (int i = l; i <= r; i++) {
if (abs(s[i].x - M) * abs(s[i].x - M) < d)
tem.push_back(i);
}
for (int i = 0; i < tem.size(); i++) {
int a = tem[i];
for (int j = i + 1;
j < tem.size() && abs(s[a].y - s[tem[j]].y) * abs(s[a].y - s[tem[j]].y) < d;
j++) // 这一层实际上的复杂度只有常数
{
d = min(d, s[a].dis(s[tem[j]]));
}
}
return d;
};
cout << fixed << setprecision(4) << sqrt((long long)(merge_sort(merge_sort, 1, n)));
return 0;
}
平面最近点对
https://sanzenin.top/posts/obsidian/平面最近点对/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取