分治-平面最近点对问题

oi wiki 中该问题的讲解。

1.P1257 平面上的最接近点对

基础款，暴力可过。

2.P1429 平面最近点对（加强版

正常款，玄学版本也能过（题解第一个做法，不过最初没卡这种方法的话应该随机情况下能过绝大多数点）。

分治解决，将集合每次分成两部分，两个部分本别先求出集合内部的最小点对的答案 d；然后找到 mid 将这个集合划分成两部分，先按照一维排序并只保留离这个划分线距离不超过 d 的。

然后按照另一维排序，枚举处理。

实际上就有很多剪枝了。sort 排序的程序复杂度是 \(O(n \log^2 n)\)，分治排序的程序复杂度是严格 \(O(n \log n)\) 的。

我不会证明复杂度，但题解区有写的很好的证明博客。请大家移步去看。

Code:

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e6+10;
int n;
int t[N];
struct node{int x,y;}s[N];
db dis(int p,int q){
	int ax=s[p].x,ay=s[p].y;
	int bx=s[q].x,by=s[q].y;
	return sqrt(1.0*(ax-bx)*(ax-bx)+1.0*(ay-by)*(ay-by));
}
bool cmp(node a,node b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
bool cmp2(int a,int b){
	return s[a].y<s[b].y;
}
db mer(int l,int r){
	db d=1e18;
	if(l==r) return d;
	if(l+1==r) return dis(l,r);
	int mid=(l+r)>>1;
	db d1=mer(l,mid),d2=mer(mid+1,r);
	d=min(d1,d2);
	int k=0;
	for(int i=l;i<=r;i++)
		if(fabs(s[mid].x-s[i].x)<d) t[++k]=i;
	sort(t+1,t+k+1,cmp2);
	for(int i=1;i<=k;i++){
		for(int j=i+1;j<=k;j++){
			if(s[t[j]].y-s[t[i]].y>=d) break;
			d=min(d,dis(t[i],t[j]));
		}
	}
	return d;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);
	sort(s+1,s+n+1,cmp);
	printf("%.4lf",mer(1,n));
	return 0;
}

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

实际上和上题的区别只是卡掉了那个玄学做法。

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e6+10;
int n;
int t[N];
struct node{int x,y;}s[N];
db dis(int p,int q){
	int ax=s[p].x,ay=s[p].y;
	int bx=s[q].x,by=s[q].y;
	return sqrt(1.0*(ax-bx)*(ax-bx)+1.0*(ay-by)*(ay-by));
}
bool cmp(node a,node b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
bool cmp2(int a,int b){
	return s[a].y<s[b].y;
}
db mer(int l,int r){
	db d=1e18;
	if(l==r) return d;
	if(l+1==r) return dis(l,r);
	int mid=(l+r)>>1;
	db d1=mer(l,mid),d2=mer(mid+1,r);
	d=min(d1,d2);
	int k=0;
	for(int i=l;i<=r;i++)
		if(fabs(s[mid].x-s[i].x)<d) t[++k]=i;
	sort(t+1,t+k+1,cmp2);
	for(int i=1;i<=k;i++){
		for(int j=i+1;j<=k;j++){
			if(s[t[j]].y-s[t[i]].y>=d) break;
			d=min(d,dis(t[i],t[j]));
		}
	}
	return d;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);
	sort(s+1,s+n+1,cmp);
	printf("%.0lf",pow(mer(1,n),2));
	return 0;
}

4.P4423 BJWC2011 最小三角形

求最近的三个点。

和上面差不多，只是确定了划分线后，只保留 fabs(s[mid].x-s[i].x)<ans/2.0 的部分。

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e6+10;
int n;
int t[N];
struct node{int x,y;}s[N];
db ans=1e18;
db dis(int p,int q){
	int ax=s[p].x,ay=s[p].y;
	int bx=s[q].x,by=s[q].y;
	return sqrt(1.0*(ax-bx)*(ax-bx)+1.0*(ay-by)*(ay-by));
}
bool cmp(node a,node b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
bool cmp2(int a,int b){
	return s[a].y<s[b].y;
}
void mer(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	mer(l,mid),mer(mid+1,r);
	int k=0;
	for(int i=l;i<=r;i++)
		if(fabs(s[mid].x-s[i].x)<ans/2.0) t[++k]=i;
	sort(t+1,t+k+1,cmp2);
	for(int i=1;i<=k;i++){
		for(int j=i+1;j<=k;j++){
			if(s[t[j]].y-s[t[i]].y>=ans/2.0) break;
			for(int q=j+1;q<=k;q++){
				if(s[t[q]].y-s[t[i]].y>=ans/2.0) break;
				ans=min(ans,dis(t[i],t[j])+dis(t[i],t[q])+dis(t[q],t[j]));
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);
	sort(s+1,s+n+1,cmp);
	mer(1,n);
	printf("%.6lf",ans);
	return 0;
}

第一节课喝了很凉的水，因为接的热水很少；第二节课长记性了，接了一杯子热水；

然后一节课没喝上水；