欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

平面最近点对

程序员文章站 2022-04-03 23:19:25
...

分治
https://blog.csdn.net/junerfsoft/article/details/2975495

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double INF = 1e20;
const int N = 100005;

struct Point{
	double x,y;
	bool operator<(const Point &rhs )const{
		return x<rhs.x;
	}
};
Point p[N];
int sp[N];

//通过y坐标排序 
bool comy ( int a, int b ){
    return p[a].y<p[b].y;
}

// 两点间的距离平方 
double dis( const Point a, const Point b ){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double solve( int L, int R ){
	//1个点 
	if( L==R ) return INF;
	//2个点 
	if( L+1==R ) return dis( p[L],p[R] );
	// 3个点 
	if( L+2 == R ){
        double m = min( dis(p[L], p[R]), dis(p[L+1], p[R]) );
        return min(m, dis(p[L], p[L+1]));
    }
    
	int m = (L+R)/2;
	//左半区域和右半区的最近点对距离 
	double d1 = solve(L,m);
	double d2 = solve(m+1,R);
	double d = min(d1,d2);
	//筛选在中线左右宽为 d 的区域内的点 
	int cnt=0;
    for( int i=m-1; i>=L&&p[m].x-p[i].x<d; --i ) sp[cnt++] = i;
	for( int i=m+1; i<=R&&p[i].x-p[m].x<d; ++i ) sp[cnt++] = i;
    //按 y 坐标排序
    sort( sp, sp+cnt, comy );
	 //两两比较
    for( int i=0; i<cnt; ++i ) {
        for( int j=i+1; j<cnt&&p[sp[j]].y-p[sp[i]].y<d; ++j ) {
            d = min( d, dis(p[sp[i]], p[sp[j]]) ) ;
        }
    } 
	return d;
}

int main()
{
	int n; 
	//freopen("in.txt","r",stdin);
	while( scanf("%d",&n)==1&&n ){
		for( int i=0; i<n; ++i ) scanf("%lf %lf",&p[i].x,&p[i].y);
		sort( p,p+n ); // 按横坐标排序 
		printf("%.2lf\n", solve(0, n-1)/2 ); //题目要求除以2
	}
	
	return 0;
}

分治的时候归并排序

https://www.cnblogs.com/Saurus/p/6119693.html
上面是把分割线左右为d的竖条里的点统计出来,然后按照y排序,然后两两比较,更新d.
这样复杂度是O(nlognlogn)。其实可以分治的时候对y归并排序,省去了sort,复杂度为O(nlogn).在杭电oj上测试,第一个730ms,第二个530ms,(虽然看上去不那么明显)。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double INF = 1e20;
const int N = 100005;

struct Point{
	double x,y;
	bool operator<(const Point &rhs )const{
		return x<rhs.x;
	}
};
Point p[N],Q[N];

// 两点间的距离平方 
double dis( const Point a, const Point b ){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double solve( int L, int R ){
	if( L==R ) return INF;
	int m = (L+R)/2;
	double d = min( solve(L,m),solve(m+1,R) ); // 递归完成后,p[L..m] 和 p[m+1..R] 都是按 y 有序的(归并排序)。 
	int tx = p[m].x; // 分割点的横坐标 
	int cnt = 0;
	for( int i = L,j = m+1; i <= m || j <= R; ++i ) {
        while(j <= R && (p[i].y > p[j].y||i > m) ) { Q[cnt++] = p[j]; ++j; }//按y归并排序
        if(abs(p[i].x - tx) < d && i <= m) { //选择分割线左边符合要求的点
        	// 此时的j满足,p[j].y>=p[i].y 且 p[j-1].y<p[j-1].y。
			//p[j]的纵坐标和p[i]相近,只需要分别检查 j 上下至多2个点就足够了。 
            for( int k = j-1; k > m && j-k < 3; --k ) d = min( d, dis(p[i],p[k]) );
            for( int k = j; k <= R && k-j < 2; ++k ) d = min( d, dis(p[i],p[k]) );
        }
        if(i <= m) Q[cnt++] = p[i];
    }
    for(int i = L, j = 0; i <= R; i++, j++) p[i] = Q[j]; // 排序结果赋给 p 
    return d;
}

int main()
{
	int n; 
	//freopen("in.txt","r",stdin);
	while( scanf("%d",&n)==1&&n ){
		for( int i=0; i<n; ++i ) scanf("%lf %lf",&p[i].x,&p[i].y);
		sort( p,p+n ); // 按横坐标排序 
		printf("%.2lf\n", solve(0, n-1)/2 );
	}
	return 0;
}

相关标签: 平面