平面最近点对的许多奇奇怪怪的做法

1、正常人的想法

法一：暴力

最直接、最简单的方法，虽然往往拿不到分。

法二：分治法1

考虑把所有的点按x排序。然后你考虑每次把他们分成一半，这样就被拆成了三个部分：

1、左边区间内部

2、右边区间内部

3、跨过了分治的分界线

因为1和2的情况可以被递归解决，所以重点说明3怎么做

你考虑先递归出1和2的答案，设为 $d$ 。

对于跨过分界线的答案，考虑每一个点和分界线的距离，那我们就不需要考虑距离比 $d$ 还要远的点了。

把满足条件的记下来，然后按 $y$ 坐标递增排序。

然后对于每一个点，暴力往后查找最近点对，如果 $y$ 坐标的差都大于 $d$ 了，就可以去统计下一个点的答案了。

注意这个时候也要实时更新 $d$。

时间复杂度 $O(n \log^2 n)$ ，复杂度瓶颈在于分治中间的按y坐标排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline double dis(node x,node y){
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double calc(int l,int r){
	if(l==r)return inf;
	if(l+1==r)return dis(p[l],p[r]);
	int cnt=0,mid=(l+r)>>1;
	double d=min(calc(l,mid),calc(mid+1,r));
	for(int i=l;i<=r;++i)
		if(fabs(p[i].x-p[mid].x)<=d)t[++cnt]=p[i];
	sort(t+1,t+cnt+1,cmp);
	for(int i=1;i<cnt;++i)
		for(int j=i+1;j<=cnt&&t[j].y-t[i].y<=d;++j)d=min(d,dis(t[i],t[j]));
	return d;
}

法三：分治2

考虑优化分治1的瓶颈，发现只要做一个类似归并的过程即可。复杂度降为 $O(n \log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline double dis(node x,node y){
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double calc(int l,int r){
	if(l==r)return inf;
	int cnt=0,mid=(l+r)>>1;ll midx=p[mid].x;
	double d=min(calc(l,mid),calc(mid+1,r));
	int pl=l,pr=mid+1;
	while(pl<=mid||pr<=r){
		if(pl<=mid&&(pr>r||p[pl].y<p[pr].y))t[++cnt]=p[pl++];
		else t[++cnt]=p[pr++];
	}
	for(int i=1;i<=cnt;++i)p[l+i-1]=t[i];
	cnt=0;
	for(int i=l;i<=r;++i)
		if(fabs(p[i].x-midx)<=d)t[++cnt]=p[i];
	for(int i=1;i<cnt;++i)
		for(int j=i+1;j<=cnt&&t[j].y-t[i].y<=d;++j)d=min(d,dis(t[i],t[j]));
	return d;
}

法四：set

这里参考了 OI Wiki 的讲解

我们考虑对于每一个元素，将它和它的左边所有元素的贡献加入到答案中。

把所有点按照 $x$ 为第一关键字、 $y$ 为第二关键字排序，并建立一个以 $y$ 为第一关键字、 $x$ 为第二关键字排序的 multiset。对于每一个位置，我们执行以下操作：

将所有满足 $x_i-x_j\geq d$ 的点从集合中删除。它们不会再对答案有贡献。

对于集合内满足 $ \lvert y_i-y_j \rvert <d $ 的所有点，统计它们和 $p_i$ 的距离。

将 $p_i$ 插入到集合中。

由于每个点最多会被插入和删除一次，所以插入和删除点的时间复杂度为
$O(n \log n)$

代码咕着

2、不正常的人想出来的办法！

声明：以下内容绝大多数都是原创，如果有类似的想法但是提出的比我早，那就是你比我早想出来的，但我确实是自己想的，不是原创的话我会标出来

1、近似排序

我们考虑一个事实，如果我们把所有的点按照 $x*y+x+y$ 排序，那么下标意义上距离这些点很近的点，大多数在真实空间内距离也很近。

感性理解一下

实在不行可以加随机偏移，比如把 $x$ 和 $y$ 全都加上一个1e7之类的东西来减小负数等极端情况带来的影响

然后在暴力比较的时候，根据我们之前的事实，可以只往后比较一些点，不需要比较到头，因为这样大概率不优。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
struct node{
	long double x,y;
	bool operator<(const node&t)const{
		return(x+102624)*(y+102624)>(t.x+102624)*(t.y+102624);
	}
};

//in main()
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
	for(int j=i+1;j<=min(i+233,n);j++)
		ans=min(ans,(long long)((a[i].x-a[j].x)*(a[i].x-a[j].x)+eps+(a[i].y-a[j].y)*(a[i].y-a[j].y)+eps));

2、随机旋转（非原创）

这个算法是参考了某人的题解

把所有的点随机旋转同一个角度。这个优化的好处是可以冲过一些坐标类hack数据。

1
2
3
4
5
6
7
8
9
mt19937 rd((unsigned long long)new char);
int theta=rd()%1000;
long double w=sin(theta),c=cos(theta);
for(int i=1;i<=n;i++){
	long long ax,ay;
	scanf("%lld%lld",&ax,&ay);
	a[i].x=1.0*ax*c-1.0*ay*w;
	a[i].y=1.0*ax*w+1.0*ay*c;
}

3、极值点法

这个方法貌似没什么人想到（

具体来说，你考虑找出 $x$ 、 $y$ 、$x*y$ 、 $x^2+y^2$ 从小到大的中间几个点，然后对它们做暴力查找查满。

4、自动优化法

首先随机选取一个起始点，找出包括那个点的答案，然后再把起始点设为答案继续找。如果你发现离 $a$ 的最近点是 $b$ ，离 $b$ 的最近点又是 $a$ ，这时你应该重新随机一个点继续执行算法。

（目前只想到了那么多…我还是太菜了