首页 > 代码库 > HD-ACM算法专攻系列(14)——Quoit Design
HD-ACM算法专攻系列(14)——Quoit Design
问题描述:
源码:
经典问题——最近邻问题,标准解法
#include"iostream" #include"algorithm" #include"cmath" using namespace std; struct Point { double x; double y; }; Point S[100000];//不使用全局变量可能会超内存 bool cmpPointX(Point a, Point b) { return a.x > b.x; } bool cmpPointY(Point a, Point b) { return a.y > b.y; } double EfficientClosestPair(Point *P, Point *Q, int start, int n) { if(n <= 3) { double result; result = (P[start].x - P[start+1].x)*(P[start].x - P[start+1].x) + (P[start].y - P[start+1].y) * (P[start].y - P[start+1].y); if(n == 3) { double tmp = (P[start].x - P[start+2].x)*(P[start].x - P[start+2].x) + (P[start].y - P[start+2].y) * (P[start].y - P[start+2].y); if(tmp < result)result = tmp; tmp = (P[start+1].x - P[start+2].x)*(P[start+1].x - P[start+2].x) + (P[start+1].y - P[start+2].y) * (P[start+1].y - P[start+2].y); if(tmp < result)result = tmp; } return result; } else { int half = n / 2; double d1 = EfficientClosestPair(P, Q, start, half); double d2 = EfficientClosestPair(P, Q, start + half, n - half); double d = d1 < d2 ? d1 : d2; double m = P[start + half - 1].x; int count = 0; double tmp; for(int i = start; i < start + n; i++) { tmp = Q[i].x - m; if(tmp < 0)tmp = - tmp; if(tmp < d)count++; } double dminsq = d; if(count > 1) { //Point *S = new Point[count]; for(int i = start, j = 0; i < start + n; i++) { tmp = Q[i].x - m; if(tmp < 0)tmp = - tmp; if(tmp < d) { S[j].x = Q[i].x; S[j].y = Q[i].y; j++; } } int k; for(int i = 0; i < count - 1; i++) { k = i + 1; while(k < count && (S[k].y - S[i].y)*(S[k].y - S[i].y) < dminsq) { dminsq = min((S[k].x - S[i].x)*(S[k].x - S[i].x) + (S[k].y - S[i].y)*(S[k].y - S[i].y), dminsq); k++; } } } return dminsq; } } int main() { int n; Point *P, *Q; cout.precision(2); cout.setf(ios::fixed); P = new Point[100000]; Q = new Point[100000]; while(scanf("%d", &n) != EOF) { if(n == 0)break; for(int i = 0; i < n; i++) { scanf("%lf %lf", &P[i].x,&P[i].y); Q[i].x = P[i].x; Q[i].y = P[i].y; } if(n <= 3) { cout<<sqrt(EfficientClosestPair(P, Q, 0, n)) / 2<<endl; } else { sort(P, P+n, cmpPointX);//使用qsort可能会超时 sort(Q, Q+n, cmpPointY); cout<<sqrt(EfficientClosestPair(P, Q, 0, n)) / 2<<endl; } } return 0; }
HD-ACM算法专攻系列(14)——Quoit Design
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。