Wall题意 已知一个多边形的城堡，现在用用最少的石头建造环绕城堡的城墙，但是城墙不能离城堡超过一定的距离L。问这个城墙最小的长度。思路 首先知道，对于一条边，我们只需将它往外平移L个长度即可，至于顶点肯定做一个半径为L的圆(一部分)将两边连接起来，如果该顶点是一个凹点，那肯定没有将两边的点直接相连短，所以需要先构造凸包(如果不知道为什么要构造凸包，可以画一下，很好看出来)。至于圆弧的那部分，需要计算角度，容易知道图中角度1和角度2互补，先将角度2利用点乘公式(不能用叉乘，因为用asin函数一个值对应两个角度)计算出来，就知道角度1了。构造凸包的算法以及模板代码中参考《挑战程序与设计竞赛》 代码
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std
;
typedef long long ll
;
typedef unsigned long ul
;
typedef unsigned long long ull
;
#define pi acos(-1.0)
#define e exp(1.0)
#define pb push_back
#define mk make_pair
#define fir first
#define sec second
#define scf scanf
#define prf printf
typedef pair
<ll
,ll
> pa
;
const int dir_4
[4][2]={-1,0,0,1,1,0,0,-1};
const int dir_8
[8][2]={-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
const ll INF
=0x3f3f3f3f3f3f3f3f;
const double eps
=1e-8;
const int MAX_N
=1e3+7;
double add(double a
,double b
){
if(fabs(a
+b
)<eps
)
return 0;
return a
+b
;
}
struct P
{
double x
,y
;
P(){}
P(double x
,double y
):x(x
),y(y
){}
P operator
+(P p
){
return P(add(x
,p
.x
),add(y
,p
.y
));
}
P operator
-(P p
){
return P(add(x
,-p
.x
),add(y
,-p
.y
));
}
P operator
*(double d
){
return P(x
*d
,y
*d
);
}
double dot(P p
){
return add(x
*p
.x
,y
*p
.y
);
}
double det(P p
){
return add(x
*p
.y
,-y
*p
.x
);
}
bool operator
<(const P
&p
)const{
if(x
!=p
.x
)
return x
<p
.x
;
return y
<p
.y
;
}
double dis(P p
){
return sqrt((x
-p
.x
)*(x
-p
.x
)+(y
-p
.y
)*(y
-p
.y
));
}
}pos
[MAX_N
],pos_hull
[MAX_N
];
double L
;
int N
,cnt
;
int main()
{
int i
,j
,k
;
scf("%d %lf",&N
,&L
);
for(i
=0;i
<N
;i
++){
scf("%lf %lf",&pos
[i
].x
,&pos
[i
].y
);
}
sort(pos
,pos
+N
);
cnt
=0;
for(i
=0;i
<N
;i
++){
while(cnt
>1&&(pos_hull
[cnt
-1]-pos_hull
[cnt
-2]).det(pos
[i
]-pos_hull
[cnt
-1])<=0)
cnt
--;
pos_hull
[cnt
++]=pos
[i
];
}
k
=cnt
;
for(i
=N
-2;i
>=0;i
--){
while(cnt
>k
&&(pos_hull
[cnt
-1]-pos_hull
[cnt
-2]).det(pos
[i
]-pos_hull
[cnt
-1])<=0)
cnt
--;
pos_hull
[cnt
++]=pos
[i
];
}
cnt
--;
double res
=0;
for(i
=0;i
<cnt
;i
++){
double dis1
=pos_hull
[i
].dis(pos_hull
[(i
-1+cnt
)%cnt
]);
double dis2
=pos_hull
[i
].dis(pos_hull
[(i
+1)%cnt
]);
res
+=dis2
;
res
+=(pi
-acos((pos_hull
[(i
+1)%cnt
]-pos_hull
[i
]).dot(pos_hull
[(i
-1+cnt
)%cnt
]-pos_hull
[i
])/dis1
/dis2
))*L
;
}
prf("%.0f\n",res
);
return 0;
}
