首页 > 代码库 > 最近点对问题 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 分治法