poj1113 Wall

Link

Solution

把多边形画出来,求出凸包。在凸包的角上分别作两边的垂线,所夹角=该角的外角。 外角和=360°,因此答案为凸包的长度加一个圆的周长。 # Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//Code by Lucida
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef double ld;
using std::sort;
using std::unique;
using std::swap;
const ld pi=acos(-1.0);
const int MAXN=1000+10;
template <class T> inline T sqr(T x){return x*x;}
template <class T> inline T abs(T x){return x>0?x:-x;}
struct vec
{
int x,y;
vec(int _x=0,int _y=0):x(_x),y(_y){}
bool operator <(const vec &a) const
{
if(x*a.y-y*a.x!=0)
return x*a.y-y*a.x>0;
return x*x+y*y<a.x*a.x+a.y*a.y;
}
bool operator ==(const vec &a) const{return x==a.x && y==a.y;}
void operator -=(vec a){x-=a.x,y-=a.y;}
void operator +=(vec a){x+=a.x,y+=a.y;}
};
typedef vec point;
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
int outer(vec a,vec b){return a.x*b.y-b.x*a.y;}
ld dist(point A,point B){return sqrt((double)sqr(A.x-B.x)+sqr(A.y-B.y));}
point p[MAXN],stack[MAXN];
int main()
{
freopen("input","r",stdin);
int top=0;
int n,L;red(n),red(L);
int mi=1;
for(int i=1;i<=n;i++)
{
red(p[i].x),red(p[i].y);
if((p[i].x<p[mi].x) || (p[i].x==p[mi].x && p[i].y<p[mi].y)) mi=i;
}
swap(p[1],p[mi]);p[0]=p[1];
for(int i=1;i<=n;i++) p[i]-=p[0];//p[1]。。。De了1h。。。。。。。
sort(p+2,p+1+n);
p[n+1]=p[1];
for(int i=1;i<=n+1;i++)
{
while(top>=2 && outer(p[i]-stack[top],stack[top]-stack[top-1])>=0) top--;
stack[++top]=p[i];
}
ld ANS=dist(stack[1],stack[top])+2*L*pi;
for(int i=1;i<top;i++) ANS+=dist(stack[i],stack[i+1]);
printf("%.0f\n",ANS);
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利