Acwing 119 (平面最近点对模板)

\(updata : 2021.12.8\)

\(sol :\) 大概来讲就是对于区间 \([l,r]\) 的最近点对的距离\(dis\) , 就是 dis = min( dis_[l , mid] , dis_[mid+1 , r] ) , 还有要考虑横跨两个子区间的点 , 可以证明在这种情况下可能会对 \(dis\) 产生影响的点的 \(x\) 的 位置就是 \([mid_x - dis , mid_x + dis]\) , 由于图太难画了 , 复习时可以考虑看 \(y\) 总的视频 ， 加上这篇题解

讲讲细节

\(① :\) 要提前对数组以 \(x\) 为第一关键字 , \(y\) 为第二关键字排序 . 我们知道二者越相近的点 , 产生的 \(dis\) 越小 , 我们越早得到越小的 \(dis\) , 对我们第三种情况的剪枝是越有效果的 ; 还有就是借此确保 \(mid_x\) 就是中间的 \(x\) .

bool cmpone(node a,node b){
	if(a.x == b.x) return a.y < b.y;
	return a.x < b.x;
	
	for(int i=1;i<=n;++i){
		scanf("%lf%lf",&pep[i].x , &pep[i].y);
		pep[i].f = 0;
	}
	for(int i=n+1;i<=n*2;++i){
		scanf("%lf%lf",&pep[i].x , &pep[i].y);
		pep[i].f = 1;
	}
	sort(pep+1 , pep+1+n*2 , cmpone);
}

\(② :\) 注意一定在递归前把 \(mid_x\) 记录下来 , 要不然对子区间 \([l,mid]\) 按 \(y\) 从小到大排序后 , 这时 \(mid_x\) 很可能不是中间的 \(x\) , 这也是前面提到的排序的作用.

	int mid = l+r>>1;
	D mid_x = pep[mid].x;
	ans = min( Dfs(l , mid) , Dfs(mid+1 , r) );

\(③ :\) 每次对区间按 \(y\) 从小到大排序 , 是为了枚举时的剪枝 , 显眼二者 \(y\) 差值大于 \(dis\) 的情况是不合法的. 同时我们可以借助递归 , 利用归并的思想 , 每次将两个区间合并即可 , 不要重复排序.

	{
		int i = l , j = mid+1 , k = 0;
		while( i<=mid && j<=r ){
			if(pep[i].y <= pep[j].y) temp[++k] = pep[i++];
			else temp[++k] = pep[j++];
		}	
		while(i<=mid) temp[++k] = pep[i++];
		while(j<=r) temp[++k] = pep[j++];
		
		for(i = 1 , j = l ; i<=k && j<=r ;++i , ++j) pep[j] = temp[i];
	} 

代码 \(:\)

#include
#include
#include
#include
using namespace std;
typedef double D;
const int N = 1e5+1;
const D inf = 1e9+1;
int T;
D ans;
struct node{
	D x,y ; 
	bool f ; 
}pep[N<<1] , temp[N<<1];
bool cmpone(node a,node b){
	if(a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}
double Dis(int a,int b){
	if(temp[a].f == temp[b].f) return inf;
	D x1 = temp[a].x , x2 = temp[b].x , y1 = temp[a].y , y2 = temp[b].y;
	return sqrt( (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) );
}
double Dfs(int l,int r){
	if(l>=r) return inf;
	int mid = l+r>>1;
	D mid_x = pep[mid].x;
	ans = min( Dfs(l , mid) , Dfs(mid+1 , r) );
	{
		int i = l , j = mid+1 , k = 0;
		while( i<=mid && j<=r ){
			if(pep[i].y <= pep[j].y) temp[++k] = pep[i++];
			else temp[++k] = pep[j++];
		}	
		while(i<=mid) temp[++k] = pep[i++];
		while(j<=r) temp[++k] = pep[j++];
		
		for(i = 1 , j = l ; i<=k && j<=r ;++i , ++j) pep[j] = temp[i];
	} //这个大括号是一个技巧 , 相当于变量的局部定义 , 可以看到k可以定义两遍.
	
	int k = 0;
	for(int i=l;i<=r;++i) 
		if(pep[i].x >= mid_x - ans && pep[i].x <= mid_x + ans) 
			temp[++k] = pep[i];
	for(int i=1;i<=k;++i)
		for(int j=i-1;j>=1;--j){
			if(temp[i].y - temp[j].y > ans) break; //剪枝
			ans = min(ans , Dis(i , j));
		}
	return ans;	
}
int main()
{
	scanf("%d",&T);
	while( T-- ){
		ans = inf;
		int n ; scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%lf%lf",&pep[i].x , &pep[i].y);
			pep[i].f = 0;
		}
		for(int i=n+1;i<=n*2;++i){
			scanf("%lf%lf",&pep[i].x , &pep[i].y);
			pep[i].f = 1;
		}
		sort(pep+1 , pep+1+n*2 , cmpone);
		printf("%.3lf\n",Dfs(1 , n*2));
	}
	return 0;
} 

\(ed：\) 对于随机数据是\(O( nlog_n)\) , 对于刻意的数据可以被卡到 \(O(n^2)\) .