求点集的凸包(Graham)

2009-02-05 14:59

#include<iostream>
#include<cmath>
using namespace std;
const int MAX_SIZE = 30;
struct point{
       double x,y;
};
point operator-(point p1,point p2);
double vp(point p1,point p2);
double sqr(double x);
class stack{
      public:
      stack(){ top = -1; }
      void pop(point& t);
      void push(point t);
      point get_top();
      bool is_empty(){ return top==-1; }
     
      private:
      point p[MAX_SIZE];
      int top;
};
void Graham_scan(point p[],int n,stack& st);
void quicksort(point p[],int i,int j,point p0);
int partition(point p[],int i,int j,point p0);
void clear(point p[],int n,point p0);
double dis(point p1,point p2);
int main(void){
    point p[MAX_SIZE],t;
    stack st;
    int n;
   
    cout<<"Input the quantity of points:";
    cin>>n;
    for(int i=0;i<n;i++){
        cout<<"Input p["<<i+1<<"]:";
        cin>>p[i].x>>p[i].y;
    }
   
    Graham_scan(p,n,st);
   
    cout<<"The result is:";
    while(!st.is_empty() ){
          st.pop(t);
          cout<<"("<<t.x<<","<<t.y<<")\t";
    }
   
    system("pause");
    return 0;
}
void Graham_scan(point p[],int n,stack& st){
     int i;
     point t1,t2;
    
     for(i=1;i<n;i++)
         if(p[i].y<p[0].y || (p[i].y==p[0].y&&p[i].x<p[0].y) ){
            t1 = p[i];
            p[i] = p[0];
            p[0] = t1;
         }
        
     quicksort(p,1,n-1,p[0]);
     clear(p,n,p[0]);
    
     st.push(p[0]);
     st.push(p[1]);
     st.push(p[2]);
    
     for(i=3;i<n;i++){
         st.pop(t1);
         while(vp(t1- st.get_top(),p[i]-t1)<=0 ) st.pop(t1);
         st.push(t1);
         st.push(p[i]);
     }
}
void quicksort(point p[],int i,int j,point p0){
     if(i>=j) return;
     int mid = partition(p,i,j,p0);
     quicksort(p,i,mid-1,p0);
     quicksort(p,mid+1,j,p0);
}
    
int partition(point p[],int i,int j,point p0){
    point k = p[i];
   
    do{
      while(i<j&& vp(p[j]-p0,k-p0)<=0.0 ) j--;
      if(i<j) p[i++] = p[j];
     
      while(i<j&& vp(p[i]-p0,k-p0)>=0.0 ) i++;
      if(i<j) p[j--] = p[i];
    }while(i!=j);
    p[i] = k;
   
    return i;
}
double vp(point p1,point p2){
       return p1.x*p2.y - p2.x*p1.y;
}
void clear(point p[],int n,point p0){
     int i,j;
    
     for(i=1;i<n-1;i++)
        if(vp(p[i]-p0,p[i+1]-p0)==0){
           if(dis(p[i],p0)>dis(p[i+1],p0) )
              p[i+1] = p[i];
           else p[i] = p[i+1];
        }
}
double dis(point p1,point p2){
       return sqrt(sqr(p1.x- p2.x) + sqr(p1.y- p2.y) );
}
double sqr(double x){
       return x*x;
}
point operator-(point p1,point p2){
      point r;
     
      r.x = p1.x - p2.x;
      r.y = p1.y - p2.y;
     
      return r;
}
point stack::get_top(){
      if(is_empty() ) return point();
      return p[top];
}
void stack::pop(point& t){
     if(is_empty() ) return;
     t = p[top--];
}
void stack::push(point t){
     if(top==MAX_SIZE-1) return;
     p[++top] = t;
}