浙江财经大学
信工学院ACM集训队

二维最近点对

本文由 Ocrosoft 于 2016-12-19 11:51:42 发表
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
using namespace std;
struct Point
{
	Point(){this->x=this->y=0;}
	Point(double x,double y){this->x=x;this->y=y;}
	double x,y;
};
double dis(Point a, Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
vector<Point> v;
double CP(int left,int right)
{
	double d=INF;
	if(left==right)return d;
	int mid=(left+right)>>1;//已排序,mid为中位点序号
	double d1=CP(left,mid);//分治
	double d2=CP(mid+1,right);
	d=min(d1,d2);//两个区间的最近点距离
	int i,j,k=0;
	vector<int> tmp;
	for(i=left;i<right;i++)
		if(abs(v[mid].x-v[i].x)<=d)
			tmp.push_back(i);//所有与中位点X坐标差小于等于最小距离的点的序号
    /*y坐标排序*/
	sort(tmp.begin(),tmp.end(),[v](const int a,const int b){return v[a].y<v[b].y;});
	for(i=0;i<tmp.size();i++)
		for(j=i+1;j<tmp.size()&&v[tmp[j]].y-v[tmp[i]].y<d;j++)
			d=min(dis(v[tmp[i]],v[tmp[j]]),d);//取最小距离
	return d;
}
int main()
{
	int n;cin>>n;
	while(n--)
	{
		double x,y;
		cin>>x>>y;
		Point p(x,y);
		v.push_back(p);
	}
	/*O(N^2)*/
	double minn=INF;
	for(int i=0;i<v.size();i++)
		for(int j=i+1;j<v.size();j++)
			minn=min(minn,dis(v[i],v[j]));
	cout<<minn<<endl;
	/*O(N*logN)*/
	sort(v.begin(),v.end(),[v](Point a,Point b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;});
	cout<<CP(0,v.size())<<endl;
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » 二维最近点对

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址