#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef int type;
struct POINT{
       type x;
       type y;
};
struct SPOINT{
       type x;
       type y;
       double ang;
};
POINT s[1001];
POINT cs[1001];
bool cmp(SPOINT a,SPOINT b){
     return a.ang<b.ang;
}
void convex_hull(int n,int &sp){
     int i,k;
     double D;
     vector<SPOINT> t(n-1);
     
      
      /*下面一小段取出y值最小的一点并把这一点放在S[0]中*/
     int tempx=s[0].x;
     int tempy=s[0].y;
     int index=0;
     for(i=1;i<n;i++)
        if((s[i].y<tempy)||((s[i].y==tempy)&&(s[i].x<tempx))){
           tempx=s[i].x;
           tempy=s[i].y;
           index=i;
        }    
     if(index!=0){
         s[index].x=s[0].x;
         s[index].y=s[0].y;
         s[0].x=tempx;
         s[0].y=tempy;
     }
     
     /*计算其它n-1个点的极角并按极角大小排序*/
     for(i=1;i<n;i++){
         t[i-1].x=s[i].x-s[0].x;
         t[i-1].y=s[i].y-s[0].y;
         t[i-1].ang=atan2((double)t[i-1].y,(double)t[i-1].x);
     }
     sort(t.begin(),t.end(),cmp);
     
     
     
     /*下面一小段计算凸包的极点并存在cs[]中，极点个数存在sp中*/
     cs[0].x=t[n-2].x;
     cs[0].y=t[n-2].y;
     cs[1].x=0;
     cs[1].y=0;
     sp=1;
     k=0;
     while(k<n-1){
         D=cs[sp-1].x*cs[sp].y+cs[sp].x*t[k].y+t[k].x*cs[sp-1].y
         -cs[sp-1].y*cs[sp].x-cs[sp].y*t[k].x-t[k].y*cs[sp-1].x;
         if(D>=0){
             sp++;
             cs[sp].x=t[k].x;
             cs[sp].y=t[k].y;
             k++;
         }
         else sp--;
     }
    
}
#define pi 3.1415926535
int main(){
    int n,radius;
    double result;
    while(scanf("%d%d",&n,&radius)!=EOF){
        for(int i=0;i<n;i++) cin>>s[i].x>>s[i].y;
        int number=0;
        convex_hull(n,number);
        
        /*下面一小段计算凸包所有边的周长*/
        result=0.0;
        for(int index=0;index<number-1;index++){
          result+=pow((cs[index+1].y-cs[index].y)*(cs[index+1].y-cs[index].y)
                  +(cs[index+1].x-cs[index].x)*(cs[index+1].x-cs[index].x),0.5);
        }
        result+=pow((cs[0].y-cs[number-1].y)*(cs[0].y-cs[number-1].y)
                  +(cs[0].x-cs[number-1].x)*(cs[0].x-cs[number-1].x),0.5);
                  
                  
        result+=2*pi*radius;
        cout.precision(0);
        cout.setf(ios::fixed);
        cout<<result<<endl;
    }
    return 0;
}

• Re:求助，大牛们帮我看看我的程序哪里错了，都WA了十几次了，先谢了！！ (21) smallwood 2009-03-01 15:08:25