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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
ConvexHull ch=new ConvexHull();
double PI=Math.acos(-1);
while(sc.hasNext()){
int n=sc.nextInt();
int l=sc.nextInt();
Point[]p=new Point[n];
for(int i=0;i<n;i++){
int x=sc.nextInt();
int y=sc.nextInt();
p[i]=new Point(x,y);
}
if(n==1){
pw.println(0);
}else if(n==2){
pw.println(Math.round(ch.dis(p[0], p[1])+Math.acos(-1)*l*2));
}else{
ch.initsort(p);
ch.graham(p);
double sum=0;
for(int i=0;i<=ch.top;i++){
sum+=ch.dis(p[ch.stack[i]],p[ch.stack[(i+1)%(ch.top+1)]]);
}
sum+=PI*l*2;
pw.println(Math.round(sum));
}
pw.flush();
}
}
}
class Point implements Comparable<Point>{
double x;
double y;
static Point k;
static double eps=1e-9;
Point(double x,double y){
this.x=x;
this.y=y;
}
Point(Point p){
this.x=p.x;
this.y=p.y;
}
@Override
public int compareTo(Point b) {
double tmp=cross(k,this,b);
if(tmp>0) return -1;
else if(Math.abs(tmp-0)<eps&&dis(k,this)<dis(k,b)) return -1;
else if(Math.abs(tmp-0)<eps&&Math.abs(dis(k,this)-dis(k,b))<eps) return 0;
else return 1;
}
double cross(Point p0,Point p1,Point p2){
return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(Point p1,Point p2){
return Math.sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
}
class ConvexHull{
double eps=1e-9;
int maxn=10000;
int[]stack;
int top;
ConvexHull(){
stack=new int[maxn];
}
double cross(Point p0,Point p1,Point p2){
return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(Point p1,Point p2){
return Math.sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
void initsort(Point []convex){
Point p0=new Point(convex[0]);
int k=0;
for(int i=1;i<convex.length;i++){
if((p0.y>convex[i].y) || ((p0.y==convex[i].y)&&(p0.x>convex[i].x)) ){
p0.x=convex[i].x;
p0.y=convex[i].y;
k=i;
}
}
convex[k]=convex[0];
convex[0]=p0;
Point.k=convex[0];
Arrays.sort(convex,1,convex.length);
}
void graham(Point []convex){
int i;
int n=convex.length;
if(n==1){
top=0;
stack[0]=0;
}
if(n==2){
top=1;
stack[0]=0;
stack[1]=1;
}
if(n>2){
for(i=0;i<=1;i++)
stack[i]=i;
top=1;
for(i=2;i<n;i++) {
while(top>0&&(cross(convex[stack[top-1]],convex[stack[top]],convex[i])<0||(Math.abs(cross(convex[stack[top-1]],convex[stack[top]],convex[i]))<eps))) top--;
top++;
stack[top]=i;
}
}
}
}
|
