images 技术分享 dmi nsq com bool sig 经典问题
问题描述:
源码:
经典问题——最近邻问题,标准解法
- #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
来源: http://www.bubuko.com/infodetail-2137274.html