用的是水平序的Graham_Scan

#include <iostream>
#include <cmath>
#include <algorithm>
const double PI=3.141592653;
using namespace std;
struct Pnt{
       double x,y;
}P[3000];
int N;
double Len;

bool cmp(const Pnt &a,const Pnt &b){
     return a.y<b.y || (a.y==b.y && a.x<b.x);
}

double CrossP(Pnt A,Pnt B,Pnt C){
    return (B.y-A.y)*(C.x-A.x)-(B.x-A.x)*(C.y-A.y);
}

double Dist(Pnt A,Pnt B){
       return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
}

void Graham_Scan(){
     int Stack[3000],Tail=1,i=2;
     bool Visit[3000];
     memset(Visit,false,sizeof(Visit));
     Stack[0]=0;
     Stack[1]=1;
     while(i<=N-1){
        if(CrossP(P[Stack[Tail-1]],P[Stack[Tail]],P[i])<=0)
           Stack[++Tail]=i++;
        else
           Tail--;
     }
     for(i=1;i<=Tail;i++)
        Visit[Stack[i]]=true;
     i=N-2;
     while(i>=0){
        if(!Visit[i]){
           if(CrossP(P[Stack[Tail-1]],P[Stack[Tail]],P[i])<=0)
              Stack[++Tail]=i--;
           else
              Tail--;
        }
        else
           i--;
     }
     double Ans=0;
     if(N!=1){
        for(int i=1;i<=Tail;i++)
           Ans+=Dist(P[Stack[i]],P[Stack[i-1]]);
     }
     Ans+=2*PI*Len;
     printf("%.lf\n",Ans);
}
int main(){
    cin>>N>>Len;
    for(int i=0;i<N;i++)
       cin>>P[i].x>>P[i].y;
    sort(P,P+N,cmp);
    Graham_Scan();
    system("pause");
    return 0;
}
    

• Re:疯狂RE，求解！！ (32) woshilalala 2011-04-06 20:00:21
  • Re:疯狂RE，求解！！ (42) laicb 2011-06-03 09:45:44