最近点对问题

2009-11-02 16:04  
传说中的分治算法：
1. 把n个点按x坐标排序。
2. 递归求解.
3. 在点的个数小于某个阈值的时候可以用枚举来搞定
4. 在每次递归的过程中要记得用归并排序的方法把点按y坐标排序，得到Y'
    这样在筛选分割线附近的点去枚举的时候才会是线性的。（因为这样可以再次降低枚举时间复杂度。。。。。。，而那个 dis(city[p],city[q])

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

struct point{
       double x,y;
};

double dis(point p1,point p2){
       return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );
}

double min(double a,double b){
       return a<b?a:b;
}

void quicksortx(int i,int j);
int partitionx(int i,int j);

int n;
point city[100010];
double mindis(int i,int j);

int main(void){
    int i,j;

    cin>>n;
    for(i=0;i<n;i++) cin>>city[i].x>>city[i].y;
   
    quicksortx(0,n-1);
    cout<<fixed<<setprecision(3)<<mindis(0,n-1)<<endl;
   
    return 0;
}

double mindis(int i,int j){
       int p,q,mid,ll,rr;
       double r;

       if(j-i<=5&&j-i>=2){
          r = 1e20;
          for(p=i;p<=j;p++)
             for(q=p+1;q<=j;q++)
                 if( r>dis(city[p],city[q]) ) r = dis(city[p],city[q]);
          
          return r;
       }
       if(i>=j) return 1e20;

       mid = (i+j)/2;
       r = min( mindis(i,mid),mindis(mid+1,j) );

       for(ll=mid-1;ll>=i;ll--)
           if(city[mid].x-city[ll].x>r) break;
       ll++;
       for(rr=mid+1;rr<=j;rr++)
           if(city[rr].x-city[mid].x>r) break;
       rr--;

       for(p=ll;p<=mid;p++)
          for(q=mid+1;q<=rr;q++){
              if(city[q].x-city[p].x>r) break;
              if(dis(city[p],city[q])<r) r = dis(city[p],city[q]);
          }

       return r;
}

void quicksortx(int i,int j){
     if(i>=j) return;
     int mid = partitionx(i,j);
     quicksortx(i,mid-1);
     quicksortx(mid+1,j);
}
   
int partitionx(int i,int j){
    point k = city[i];

    do{
      while(i<j&&city[j].x>=k.x) j--;
      if(i<j) city[i++] = city[j];

      while(i<j&&city[i].x<=k.x) i++;
      if(i<j) city[j--] = city[i];
    }while(i!=j);
    city[i] = k;

    return i;
}