862 字
4 分钟
平面最近点对

问题
给定平面上任意n个点,求最近的一对点之间的距离
思路
我们使用类似于归并排序的思想解决这道题目.归并排序的思想是,如果一个区间的答案能够由二分划出的左区间,右区间,同时能够通过常数复杂度得到跨越mid左右区间的元素组成的答案,那么我们就可以以的复杂度解决这道题目. 容易想到,我们可以对x坐标进行排序,然后每次递归处理左右两个区间并取答案最小值. 所以问题就是,我们如何通过常数复杂度得到跨越mid的答案? 我们可以先做一些剪枝操作:
- 如果横坐标距离mid的x坐标大于等于已经得出的当前最小d,可以之间不参与计算
- 如果两个点的y坐标之差大于等于d,当前点以及比这个点y坐标大的点都不可以参与计算.
然后这次暴力枚举跨越左右区间答案的过程就神奇的变成了常数*n复杂度喵!
接下来给出证明:
我们假设以及对y排好序,我们要找所有和当前点b距离最小的点,经过剪枝之后,我们实际上把当前点和所有可以匹配的点限制在了(2*d)*d的一个矩形区域内,即8个边长为的小正方形,这个小正方形的对角线为,小于d,但是当前两个点之间的距离最小是d,故一个小正方形内不可能有两个以上点,一次一个点最多只会和7个点参与计算.
CSES Minimum Euclidean Distance P1429 平面最近点对(加强版)
#include <algorithm>#include <bits/stdc++.h>#define N 1000005#define pr pair<ll, ll>#define ll __int128using 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;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时