poj 1113 Wall 凸包

 1 /**
 2 大意：给定点，求将这些点包起来的，最小周长，，形成的凸包与点之间的需要有一定的距离l；
 3 思路： 1、求出凸包
 4           2、求凸包中的长度+ 弧形的长度----〉即一个圆的周长： 因为形成的多边形的内角是360 所以因为距离l所形成的弧的角度相加即为360.。也就是一个圆的周长。。
 5 值得学习：对于四舍五入。（int）（ans+ 0.5）
 7 
 8 **/
 9 /#include <iostream>
10 #include <algorithm>
11 #include <cmath>
12 using namespace std;
13 const int maxn = 1050;
14 const double pi = acos(-1.0);
15 const double eps = 1e-8;
16 int dcmp(double x){
17     if(fabs(x)<eps) return 0;
18     else
19         return x<0?-1:1;
20 }
21 int n;
22 struct point{
23     double x,y;
24     point (double x=0,double y=0):x(x),y(y){}
25 };
26 point p[maxn];
27 point ch[maxn];
28 typedef point Vector;
29 Vector operator - (point a , point b){
30     return Vector (a.x-b.x,a.y-b.y);
31 }
32 
33 double cross(Vector a,Vector b){
34     return a.x*b.y-a.y*b.x;
35 }
36 double length(Vector a){
37     return sqrt(a.x*a.x+a.y*a.y);
38 }
39 bool cmp(point a ,point b){
40     if(a.x==b.x)
41         return a.y<b.y;
42     return a.x<b.x;
43 }
44 int convexHull(point *p,int n,point *ch){   //   凸包求法。
45     //cout<<"--------------->"<<endl;
46     sort(p,p+n,cmp);
47    // for(int i=0;i<n;i++)
48     //    cout<<p[i].x<<" "<<p[i].y<<endl;
49     int m =0;
50     for(int i=0;i<n;i++){
51         while(m>1&&dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)
52             m--;
53         ch[m++] = p[i];
54     }
55     int k= m;
56     for(int i=n-2;i>=0;i--){
57         while(m>k&&dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0)
58             m--;
59         ch[m++] = p[i];
60     }
61     //cout<<m<<endl;
62     if(n>1) m--;
63     return m;
64 }
65 
66 int main()
67 {
68     int n,l;
69     cin>>n>>l;
70     for(int i=0;i<n;i++){
71         cin>>p[i].x>>p[i].y;
72     }
73     int res = convexHull(p,n,ch);
74     //for(int i=0;i<res;i++)
75      //   cout<<ch[i].x<<" "<<ch[i].y<<endl;
76     double ans =0;
77     for(int i=0;i<res-1;i++){
78         ans += length(ch[i+1]-ch[i]);
79     }
80     ans += length(ch[res-1]-ch[0]);
81    //cout<<ans<<endl;
82     ans += pi*l*2;
83     cout<<(int )(ans+0.5)<<endl;
84     return 0;
85 }