这是一道非常经典的题目。
首先可以想到暴力的算法,一一匹配取最小值,期望时间复杂度为 $O(n^2)$,很明显过不了此题。
所以我们考虑分治,我们每次将所有点按 x 分为两半,然后分治两半,取最小值,然后就可以获取到左右两块内部最小值,那么大范围内的最小值只有左边最小值,右边最小值或者横跨左右的最小值。我们假设d=min(左边,右边)
那么易得横跨左右的最小值中左右端点肯定在 $x\in[x_{mid} - d,x_{mid} + d]$ 的点之间。那么我们取出所有符合的点后按 y 排序,就暴力合并左右,显然对于每个点 i,只要考虑取出的点中 $y\in[y_i, y_i + d]$ 的点就好了。
暴力看起来慢,但是实际上可以证明对于每个点只有很少的点符合这个值(虽然我不会)
因为 sqrt 为浮点数,所有为保证精度,我就将所有距离的平方值存了下来,然而要注意寻找符合范围的点要以 sqrt 值为标准。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 4e5 + 5;
const long long inf = 9e18;
struct node {
long long x, y;
}no[N], tmp[N];
int n;
inline long long read(){
long long w = 1, s = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') w = -w;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
s = (s<<3) + (s<<1) + (ch^48);
ch = getchar();
}
return w * s;
}
bool cmp(node a, node b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool cmp1(node a, node b) {
return a.y < b.y;
}
long long dist(node i, node j) {
return (i.x - j.x) * (i.x - j.x) + (i.y - j.y) * (i.y - j.y);
}
long long merge(int l, int r) {
if (l == r) return inf;
if (r == l + 1) return dist(no[l], no[r]);
int mid = l + r >> 1;
long long ans = min(merge (l, mid), merge (mid + 1, r)), tmpp;
double ttmp = sqrt(ans);
int cnt = 0;
for (int i = l;i <= r; ++ i)
if (abs (no[i].x - no[mid].x) < ttmp)
tmp[++ cnt] = no[i];
sort (tmp + 1, tmp + cnt + 1, cmp1);
for (int i = 1;i < cnt; ++ i)
for (int j = i + 1;j <= cnt && tmp[j].y < tmp[i].y + ttmp; ++ j) {
tmpp = dist(tmp[i], tmp[j]);
if (tmpp < ans)
ans = tmpp;
}
return ans;
}
int main() {
scanf ("%d", &n);
for (int i = 1;i <= n; ++ i) {
no[i].x = read();
no[i].y = read();
}
sort (no + 1, no + n + 1, cmp);
// printf ("%lld", merge (1, n)); // 加强加强版输出
printf ("%.4lf", sqrt (merge (1, n))); // 加强版输出
return 0;
}
标签:ch,加强版,int,P7883,long,最小值,&&
From: https://www.cnblogs.com/Assassins-Creed/p/18018375