题解：计算凸包……
|
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 |
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath>using
namespace std; struct
node{int
x,y;}vex[1005],stackf[1005]; bool
cmp1(node a,node b){ if(a.y==b.y)return
a.x<b.x; else
return a.y<b.y; } int
cross(node a,node b,node c){return
(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);} double
dis(node a,node b){return
sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));} bool
cmp2(node a,node b){ int
m=cross(vex[0],a,b); if(m==0)return
dis(vex[0],a)-dis(vex[0],b)<=0?1:0; else
return m>0?1:0; } int
main(){ int
t; while(scanf("%d",&t),t!=0){ for(int
i=0;i<t;i++)scanf("%d%d",&vex[i].x,&vex[i].y); if(t==1)printf("%.2f\n",0.00); else
if(t==2)printf("%.2f\n",dis(vex[0],vex[1])); else{ sort(vex,vex+t,cmp1); sort(vex+1,vex+t,cmp2); memset(stackf,0,sizeof(stackf)); stackf[0]=vex[0]; stackf[1]=vex[1]; int
top=1; for(int
i=2;i<t;i++){ while(i>=1&&cross(stackf[top-1],stackf[top],vex[i])<0)top--; stackf[++top]=vex[i]; } double
s=0; for(int
i=1;i<=top;i++)s+=dis(stackf[i-1],stackf[i]); s+=dis(stackf[top],vex[0]); printf("%.2f\n",s); } } return
0;} |
HDU 1392 Surround the Trees,布布扣,bubuko.com
原文：http://www.cnblogs.com/forever97/p/3650021.html