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;
}