HDU 1392 Surround the Trees
传送门：http://acm.split.hdu.edu.cn/showproblem.php?pid=1392 题目翻译 求N个点组成的图形的周长，两个点的情况只算其距离。 题解 凸包模板 代码
|
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 |
#include<stdio.h> #include<math.h> #include<algorithm> #include<iostream> using namespace std; const int MAXN=1000; struct point{ int x,y; }; int n; point list[MAXN+5]; int stack[MAXN+5],top; int 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 sqrt((double)(p2.x-p1.x)*(double)(p2.x-p1.x)+(double)(p2.y-p1.y)*(double)(p2.y-p1.y)); } bool cmp(point p1,point p2){ int tmp=cross(list[0],p1,p2); if(tmp>0) return true; else if(tmp==0&&dis(list[0],p1)<dis(list[0],p2)) return true; else return false; } void init(int n){ int i,k; point p0; scanf("%d%d",&list[0].x,&list[0].y); p0.x=list[0].x; p0.y=list[0].y; k=0; for(i=1;i<n;i++){ scanf("%d%d",&list[i].x,&list[i].y); if( (p0.y>list[i].y) || ((p0.y==list[i].y)&&(p0.x>list[i].x)) ){ p0.x=list[i].x; p0.y=list[i].y; k=i; } } list[k]=list[0]; list[0]=p0; sort(list+1,list+n,cmp); } void graham(int n){ int i; 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(list[stack[top-1]],list[stack[top]],list[i])<=0) top--; top++; stack[top]=i; } } } int main(){ while(scanf("%d",&n)!=EOF){ if(n==0) break; init(n); graham(n); double Ans=0; stack[++top]=stack[0]; for (int i=0;i<top;i++) Ans+=dis(list[stack[i]],list[stack[i+1]]); if (n==2) Ans/=2.0; printf("%.2f\n",Ans); } return 0; } |
