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
| #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct point{
double x,y;
}a[maxn],b[maxn];
bool mult(point p0,point p1,point p2){
return (p1.x-p0.x)*(p2.y-p0.y)>=(p2.x-p0.x)*(p1.y-p0.y);
}
bool operator<(const point &p1,const point &p2){
return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);
}
int graham(point pnt[],int n,point res[]){
int i,len,top=1;
sort(pnt,pnt+n);
if(n==0) return 0;
res[0]=pnt[0];
if(n==1) return 1;
res[1]=pnt[1];
if(n==2) return 2;
res[2]=pnt[2];
for(i=2;i<n;i++){
while(top&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
len=top;res[++top]=pnt[n-2];
for(i=n-3;i>=0;i--){
while(top!=len&&mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
return top;
}
int main(){
int t;scanf("%d",&t);
while(t--){
int n,l;scanf("%d%d",&n,&l);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
int k=graham(a,n,b);
double ans=0;
for(int i=0;i<k-1;++i)
ans+=sqrt((b[i].x-b[i+1].x)*(b[i].x-b[i+1].x)+(b[i].y-b[i+1].y)*(b[i].y-b[i+1].y));
if(k>2) ans+=sqrt((b[k-1].x-b[0].x)*(b[k-1].x-b[0].x)+(b[k-1].y-b[0].y)*(b[k-1].y-b[0].y));
ans+=2*acos(-1)*l;
printf("%.0lf\n",ans);
if(t) printf("\n");
}
return 0;
}
|