Poj 1113 Wall

  1 /* 二维几何  */
  2 /* 需要包含的头文件 */
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cmath >
  6 #include <iostream>
  7 #include <algorithm>
  8 
  9 using namespace std;
 10 /** 常用的常量定义 **/
 11 const double INF  = 1e200;
 12 const double eps  = 1e-10;
 13 const double PI  = acos(-1.0);
 14 const int Max = 1e6;
 15 
 16 /** 基本几何结构 **/
 17 struct Point
 18 {
 19     double x,y;
 20     Point(double a=0, double b=0){x=a,y=b;}
 21     bool operator<(const Point &ta)const
 22     {
 23         if(x==ta.x)     return y<ta.y;
 24         return x<ta.x;
 25     }
 26     friend Point operator+(const Point &ta,const Point &tb)
 27     {
 28         return Point(ta.x+tb.x,ta.y+tb.y);
 29     }
 30     friend Point operator-(const Point &ta,const Point &tb)
 31     {
 32         return Point(ta.x-tb.x,ta.y-tb.y);
 33     }
 34 };
 35 struct Vec2D        ///二维向量，*重载为点乘，/重载为叉乘
 36 {
 37     double x,y;
 38     Vec2D(double ta,double tb){x=ta,y=tb;}
 39     Vec2D(Point &ta){x=ta.x,y=ta.y;}
 40     friend double operator*(const Vec2D &ta,const Vec2D &tb)
 41     {
 42         return ta.x*tb.x+ta.y*tb.y;
 43     }
 44     friend double operator/(const Vec2D &ta,const Vec2D &tb)
 45     {
 46         return ta.x*tb.y-ta.y*tb.x;
 47     }
 48     friend Vec2D operator+(const Vec2D &ta,const Vec2D &tb)
 49     {
 50         return Vec2D(ta.x+tb.x,ta.y+tb.y);
 51     }
 52     friend Vec2D operator-(const Vec2D &ta,const Vec2D &tb)
 53     {
 54         return Vec2D(ta.x-tb.x,ta.y-tb.y);
 55     }
 56     Vec2D operator=(const Vec2D &ta)
 57     {
 58         x=ta.x,y=ta.y;
 59         return *this;
 60     }
 61 };
 62 struct LineSeg      ///线段，重载了/作为叉乘运算符，*作为点乘运算符
 63 {
 64     Point s,e;
 65     LineSeg(){s=Point(0,0),e=Point(0,0);}
 66     LineSeg(Point a, Point b){s=a,e=b;}
 67     double lenth(void)
 68     {
 69         return sqrt((s.x-e.x)*(s.x-e.x)+(s.y-e.y)*(s.y-e.y));
 70     }
 71     friend double operator*(const LineSeg &ta,const LineSeg &tb)
 72     {
 73         return (ta.e.x-ta.s.x)*(tb.e.x-tb.s.x)+(ta.e.y-ta.s.y)*(tb.e.y-tb.s.y);
 74     }
 75     friend double operator/(const LineSeg &ta,const LineSeg &tb)
 76     {
 77         return (ta.e.x-ta.s.x)*(tb.e.y-tb.s.y)-(ta.e.y-ta.s.y)*(tb.e.x-tb.s.x);
 78     }
 79     LineSeg operator=(const LineSeg &ta)
 80     {
 81         s=ta.s,e=ta.e;
 82         return *this;
 83     }
 84 };
 85 struct Line         /// 直线的解析方程 a*x+b*y+c=0  为统一表示，约定 a >= 0
 86 {
 87     double a,b,c;
 88     Line(double d1=1, double d2=-1, double d3=0){ a=d1,b=d2,c=d3;}
 89 };
 90 
 91 double getdis(const Point &ta,const Point &tb);
 92 bool cmp(const Point &ta,const Point &tb);
 93 void graham(Point ps[],Point tb[],int n,int &num);
 94 void ConvexClosure(Point ps[],Point tb[],int n,int &num);
 95 
 96 Point ps[1100],tb[1100];
 97 int n,l,num;
 98 double ans;
 99 
100 int main(void)
101 {
102     cin>>n>>l;
103     for(int i=0,x,y;i<n;i++)
104         scanf("%d%d",&x,&y),ps[i]=Point(x,y);
105     graham(ps,tb,n,num);
106     //for(int i=0;i<num;i++)
107     //    printf("%f %f\n",tb[i].x,tb[i].y);
108     tb[num++]=tb[0];
109     LineSeg lx;
110     ans+=2*PI*l;
111     for(int i=1;i<num;i++)
112     {
113         lx.s=tb[i-1],lx.e=tb[i];
114         ans+=lx.lenth();
115     }
116     printf("%d\n",(int)(0.5+ans));
117     return 0;
118 }
119 
120 double getdis(const Point &ta,const Point &tb)
121 {
122 
123     return sqrt((ta.x-tb.x)*(ta.x-tb.x)+(ta.y-tb.y)*(ta.y-tb.y));
124 }
125 /** ************凸包算法****************
126         寻找凸包的graham 扫描法
127         PS(PointSet)为输入的点集；
128         tb为输出的凸包上的点集，按照逆时针方向排列;
129         n为PointSet中的点的数目
130         num为输出的凸包上的点的个数
131 ****************************************** **/
132 bool cmp(const Point &ta,const Point &tb)
133 {
134     double tmp=LineSeg(ps[0],ta)/LineSeg(ps[0],tb);
135     if(fabs(tmp)<eps)
136         return getdis(ps[0],ta)<getdis(ps[0],tb);
137     else if(tmp>0)
138         return 1;
139     return 0;
140 }
141 void graham(Point ps[],Point tb[],int n,int &num)
142 {
143     int cur=0,top=2;
144     for(int i=1;i<n;i++)
145         if(ps[cur].y>ps[i].y || (ps[cur].y==ps[i].y &&ps[cur].x>ps[i].x))
146             cur=i;
147     swap(ps[cur],ps[0]);
148     sort(ps+1,ps+n,cmp);
149     tb[0]=ps[0],tb[1]=ps[1],tb[2]=ps[2];
150     for(int i=3;i<n;i++)
151     {
152         while(LineSeg(tb[top-1],tb[top])/LineSeg(tb[top-1],ps[i])<0)
153             top--;
154         tb[++top]=ps[i];
155     }
156     num=top+1;
157 }
158 /** 卷包裹法求点集凸壳，参数说明同graham算法 **/
159 void ConvexClosure(Point ps[],Point tb[],int n,int &num)
160 {
161     LineSeg lx,ly;
162     int cur,ch;
163     bool vis[Max];
164     num=-1,cur=0;
165     memset(vis,0,sizeof(vis));
166     for(int i=1;i<n;i++)
167         if(ps[cur].y>ps[i].y || (ps[cur].y==ps[i].y &&ps[cur].x>ps[i].x))
168             cur=i;
169     tb[++num]=ps[cur];
170     lx.s=Point(ps[cur].x-1,ps[cur].y),lx.e=ps[cur];
171     /// 选取与最后一条确定边夹角最小的点，即余弦值最大者
172     while(1)
173     {
174         double mxcross=-2,midis,tmxcross;
175         ly.s=lx.e;
176         for(int i=0;i<n;i++)if(!vis[i])
177         {
178             ly.e=ps[i];
179             tmxcross=(lx*ly)/lx.lenth()/ly.lenth();
180             if((fabs(tmxcross-mxcross)<eps && getdis(ly.s,ly.e)<midis) || tmxcross>mxcross)
181                 mxcross=tmxcross,midis=getdis(ly.s,ly.e),ch=i;
182         }
183         if(ch==cur)break;
184         tb[++num]=ps[ch],vis[ch]=1;
185         lx.s=tb[num-1],lx.e=tb[num],ly.s=tb[num];
186     }
187     num++;
188 }