【luogu P1257】【luogu P1429】平面上的最接近点对 / 平面最近点对(加强版)
程序员文章站
2022-05-12 14:57:08
...
平面上的最接近点对 / 平面最近点对(加强版)
题目链接:luogu P1257 / luogu P1429
题目大意
给你平面上的一堆点,要你找距离最近的两个的距离。
思路
就直接上分治,不会平面分治的可以看这个。
代码
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 2000000000.0
using namespace std;
struct zb {
double x, y;
}a[200001], tmp[200001];
int n, tn;
double dis(zb x, zb y) {
return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
bool cmpx(zb x, zb y) {
return x.x < y.x;
}
bool cmpy(zb x, zb y) {
return x.y < y.y;
}
double slove(int l, int r) {
double re;
if (l == r) return INF;
int mid = (l + r) >> 1;
re = min(slove(l, mid), slove(mid + 1, r));
tn = 0;
for (int i = mid; i >= l && a[mid].x - a[i].x < re; i--)
tmp[++tn] = a[i];
for (int i = mid + 1; i <= r && a[i].x - a[mid].x < re; i++)
tmp[++tn] = a[i];
sort(tmp + 1, tmp + tn + 1, cmpy);
for (int i = 1; i <= tn; i++)
for (int j = i + 1; j <= tn && tmp[j].y - tmp[i].y < re; j++)
re = min(re, dis(tmp[i], tmp[j]));
return re;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lf %lf", &a[i].x, &a[i].y);
sort(a + 1, a + n + 1, cmpx);
printf("%.4lf", slove(1, n));
return 0;
}
上一篇: Doug Lea了解下