首页 > 代码库 > 平面最近点对
平面最近点对
HDU 1007 求平面最近点对距离的一半
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> using namespace std; const double eps = 1e-7; const int MAXN = 100010; const double INF = 1e20; struct Point { double x,y; }; double dist(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } Point p[MAXN]; Point tmpt[MAXN]; bool cmpxy(Point a,Point b) { if(a.x != b.x)return a.x < b.x; else return a.y < b.y; } bool cmpy(Point a,Point b) { return a.y < b.y; } double Closest_Pair(int left,int right) { double d = INF; if(left == right)return d; if(left + 1 == right) return dist(p[left],p[right]); int mid = (left+right)/2; double d1 = Closest_Pair(left,mid); double d2 = Closest_Pair(mid+1,right); d = min(d1,d2); int k = 0; for(int i = left;i <= right;i++) { if(fabs(p[mid].x - p[i].x) <= d) tmpt[k++] = p[i]; } sort(tmpt,tmpt+k,cmpy); for(int i = 0;i <k;i++) { for(int j = i+1;j < k && tmpt[j].y - tmpt[i].y < d;j++) { d = min(d,dist(tmpt[i],tmpt[j])); } } return d; } int main() { int n; while(~scanf("%d",&n) && n) { for(int i = 0;i < n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p,p+n,cmpxy); printf("%.2lf\n",Closest_Pair(0,n-1)/2); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。