学步园

第一次做凸包，用的水平序Grahm-Scan

 var<br /> q:array[0..3000]of longint;<br /> x,y:array[0..1100]of comp;<br /> n,m,i,j,k,r:longint;<br /> ans:double;<br /> procedure init;<br /> begin<br /> readln(n,r);<br /> for i:=1 to n do readln(x[i],y[i]);<br /> end;<br /> procedure kp(s,t:longint);<br /> var<br /> i,j:longint;<br /> xx,yy,tt:comp;<br /> begin<br /> i:=s;j:=t;xx:=x[(i+j)>>1];yy:=y[(i+j)>>1];<br /> repeat<br /> while (y[i]<yy)or( (y[i]=yy)and(x[i]<xx) ) do inc(i);<br /> while (y[j]>yy)or( (y[j]=yy)and(x[j]>xx) ) do dec(j);<br /> if i<=j then<br /> begin<br /> tt:=y[i];y[i]:=y[j];y[j]:=tt;<br /> tt:=x[i];x[i]:=x[j];x[j]:=tt;<br /> inc(i);dec(j)<br /> end;<br /> until i>j;<br /> if i<t then kp(i,t);if j>s then kp(s,j);<br /> end;<br /> function check(a,b,c:longint):boolean;<br /> begin<br /> exit((x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])>=0);<br /> end;<br /> function ll(a,b:longint):double;<br /> begin<br /> exit(sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b])));<br /> end;<br /> procedure doit;<br /> var<br /> i,j,k,t:longint;<br /> begin<br /> kp(1,n);q[1]:=1;q[2]:=2;t:=2;<br /> for i:=3 to n do<br /> begin<br /> inc(t);q[t]:=i;<br /> while (t>2) and not check(q[t-2],q[t-1],q[t]) do<br /> begin<br /> dec(t);q[t]:=q[t+1];<br /> end;<br /> end;<br /> for i:=n-1 downto 1 do<br /> begin<br /> inc(t);q[t]:=i;<br /> while (t>2) and not check(q[t-2],q[t-1],q[t]) do<br /> begin<br /> dec(t);q[t]:=q[t+1];<br /> end;<br /> end;<br /> ans:=2*pi*r;<br /> for i:=1 to t-1 do ans:=ans+ll(q[i],q[i+1]);<br /> ans:=ans+ll(q[t],q[1]);<br /> writeln(round(ans));<br /> end;<br /> begin<br /> init;<br /> doit;<br /> end.<br />