首页 > 代码库 > 最近点对问题 HDU Quoit Design 1007 分治法
最近点对问题 HDU Quoit Design 1007 分治法
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<stack>#include<string>#include<queue>using namespace std;const int maxn = 100005;const long long INF = 0xfffffff;struct Point{ double x, y;}P[maxn], Temp[maxn];bool cmp(Point a, Point b){ if(a.x != b.x) return a.x < b.x; return a.y < b.y;}bool cmpy(Point a, Point b){ return a.y < b.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) );}double Colosest(int L,int R){ if(L == R) return INF; if(L + 1 == R) return dis(P[L],P[R]); int Mid = (L + R) / 2; double d1 = Colosest(L, Mid); double d2 = Colosest(Mid + 1, R);
double d = min(d1, d2);
//递归找左右两侧的点,最小距离 int k = 0; for(int i = Mid; i >= L; i--) { if( P[Mid].x - P[i].x < d ) Temp[k++] = P[i]; else break; } for(int j = Mid + 1; j <= R; j++) { if(P[j].x - P[Mid].x < d) Temp[k++] = P[j]; else break; }//找出在中间点的可能点对 然后排序 sort(Temp,Temp+k,cmpy); for(int i=0; i<k; i++) {
/*需要一个 Temp[j].y - Temp[i].y < d 优化, 不然会超时*/ for(int j=i+1; j < k && Temp[j].y - Temp[i].y < d ; j++) { double d3 = dis(Temp[j], Temp[i]); if(d3 < d) d = d3; } } 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,cmp);//先排序 printf("%.2lf\n", Colosest(0,n-1)/2 ); } return 0;}
最近点对问题 HDU Quoit Design 1007 分治法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。