P1429 平面最近点对（加强版）【芙芙】

平面最近点对（加强版）

题目背景

P7883 平面最近点对（加强加强版）

题目描述

给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的

输入格式

第一行：$n$ ，保证 $2\le n\le 200000$ 。

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

输出格式

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

样例 #1

样例输入 #1

3
1 1
1 2
2 2
1
2
3
4

样例输出 #1

1.0000
1

提示

数据保证 $0\le x,y\le 10^9$

人类智慧高光时刻

P1429 平面最近点对（加强版）里最高赞题解写道：

我们充分发扬人类智慧：
将所有点全部绕原点旋转同一个角度，然后按 xx 坐标排序
根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远
所以我们只取每个点向后的 5 个点来计算答案
这样速度快得飞起，在 n=1000000 时都可以在 1 s 内卡过
1
2
3
4
5

AC CODE

#include<bits/stdc++.h>
#define pie acos(-1.0)
#define int long long int
using namespace std;
const int N=4e5+124;
int n;
int ans=1e16;
struct node{
	int x,y;	
}a[N];
bool cmp(node x,node y){
	return x.x<y.x;
}
int dist(int aa,int bb,int ac,int bc){
	return (aa-ac)*(aa-ac)+(bb-bc)*(bb-bc);
}
void work(double ang){
	ang=ang/180.0*pie;
	for(int i=1;i<=n;i++){
		int ax=a[i].x,ay=a[i].y;
		int ex,ey;
//		ex=ax*cos(ang)-ay*sin(ang);
//		ey=ax*sin(ang)-ay*cos(ang);
		ex=(ax-0.0)*cos(ang)-(ay-0.0)*sin(ang)+0.0;
		ey=(ax-0.0)*sin(ang)+(ay-0.0)*cos(ang)+0.0;
		a[i].x=ex,a[i].y=ey;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=i+100&&j<=n;j++){
			if(i==j)continue;
//			ans=min(ans,dist(a[i].x,a[i].y,a[j].x,a[j].y));
			if(ans>dist(a[i].x,a[i].y,a[j].x,a[j].y)){
				ans=dist(a[i].x,a[i].y,a[j].x,a[j].y);
			}
		}
	}
}
signed main(){
	cin>>n;
	srand(time(NULL));
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	work(0);
	work(rand()%360);
	work(rand()%360);
	printf("%d\n",ans);
	return 0;
}
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

封面