洛谷 P1429 平面最近点对（加强版）kd树

缘起

日常浪费生命~ 洛谷 P1429 平面最近点对（加强版）

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
题目描述
给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的

输入格式
第一行：n；2≤n≤200000

接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式
仅一行，一个实数，表示最短距离，精确到小数点后面4位。

输入输出样例
输入 #1复制
3
1 1
1 2
2 2
输出 #1复制
1.0000
说明/提示
0<=x,y<=10^9

完全套用 【1】， 又水了一道题~ 诶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define SQUARE(x) ((x)*(x))
//#define LOCAL
const int maxn = 200005;
#define DBL_MAX 1.7976931348623158e+300
int n;

struct Point
{
	double x, y;
}p[maxn];
int pp[maxn]; // 用于收集处于带型区域的点集的索引

bool cmpx(Point &a, Point &b) //按照x升序
{
	return a.x<b.x;
}

bool cmpy(int a, int b) // 按照y升序
{
	return p[a].y<p[b].y;
}

double dis(int i, int j) 
{
	return sqrt(SQUARE(p[i].x-p[j].x)+SQUARE(p[i].y-p[j].y));
}

double fz(int lo, int hi)
{
	if (lo>=hi)
	{
		return DBL_MAX;
	}
	int mid = (lo+hi)>>1;
	double a = fz(lo, mid), b = fz(mid+1, hi);
	double ans = min(a,b);
	int cnt = 0; // 收集到的位于带型区域中的点的个数
	for (int i = lo; i<=hi; i++)
	{
		if (p[i].x>=p[mid].x-ans && p[i].x<=p[mid].x+ans)
		{
			pp[cnt++] = i;
		}
	} // 收集位于带型区域中的点集
	sort(pp,pp+cnt, cmpy); // 按照y坐标升序
	for (int i = 0; i<cnt-1; i++)
	{
		for (int j = i+1; j<cnt; j++)
		{
			if (p[pp[j]].y-p[pp[i]].y>=ans)
			{
				break; // 因为关于y升序排过序了
			}
			ans = min(ans, dis(pp[i],pp[j]));
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d", &n))
	{
		for (int i = 0; i< n; i++)
		{
			scanf("%lf%lf", &p[i].x, &p[i].y);
		}
		sort(p, p+n, cmpx); // 按照x升序
		printf("%.4lf\n",fz(0,n-1));
	}
	return 0;
}

ac情况

1
2
3
4
5
6
7
8
所属题目
P1429 平面最近点对（加强版）
评测状态
Accepted
评测分数
100
提交时间
2019-09-23 15:26:49

参考

【1】https://yfsyfs.github.io/2019/09/22/hdu-1007-Quoit-Design-%E6%9F%A5%E6%89%BE%E5%B9%B3%E9%9D%A2%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9/