【POJ1113】Wall（凸包）

【题目】

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Maxn 1010

 struct Point

 {

     double x,y;

     Point(double x=,double y=):x(x),y(y) {}

 };

 typedef Point Vector;

 Point p[Maxn];

 int n,l;

 const double pi=3.1415926535898;

 double myabs(double x) {return x<?-x:x;}

 const double eps=1e-;

 int dcmp(double x)//判断正负和零

 {

     if(myabs(x)<eps) return ;

     else return x<?-:;

 }

 Vector operator - (Point A,Point B) {return Vector(A.x-B.x,A.y-B.y);}

 double Dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}

 double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}

 double Length(Vector A) {return sqrt(Dot(A,A));}

 bool cmp(Point x,Point y) {return dcmp(x.x-y.x)==?(x.y<y.y):(x.x<y.x);}

 Point ch[Maxn];int len=;

 void covexhull()

 {

     for(int i=;i<=n;i++)

     {

         while(len>&&Cross(ch[len]-ch[len-],p[i]-ch[len-])<=) len--;

         ch[++len]=p[i];

     }int k=len;

     for(int i=n-;i>=;i--)

     {

         while(len>k&&Cross(ch[len]-ch[len-],p[i]-ch[len-])<=) len--;

         ch[++len]=p[i];

     }

     if(n>) len--;

 }

 double PolygonLength()

 {

     double L=;

     for(int i=;i<=len;i++)

         L+=Length(ch[i]-ch[i-]);

     L+=Length(ch[]-ch[len]);

     return L;

 }

 int main()

 {

     scanf("%d%d",&n,&l);

     for(int i=;i<=n;i++)

     {

         scanf("%lf%lf",&p[i].x,&p[i].y);

     }

     sort(p+,p++n,cmp);

     covexhull();

     printf("%.0f\n",PolygonLength()+pi*l*);

     return ;

 }

[POJ1113]

2016-04-28 19:32:02