欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【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;
}