生活随笔
收集整理的這篇文章主要介紹了
hdu 1392 Surround the Trees
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
凸包模板
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;const int N=105;
const double eps=1e-8;struct point{double x;double y;
}p[N], stack[N];bool isZero(double x){return (x>0 ? x : -x) <eps;
}double dis(point A,point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}double crossProd(point A,point B,point C){return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}int cmp(const void *a, const void *b) {point *c = (point *)a;point *d = (point *)b;double k = crossProd(p[0], *c, *d);//極角大小轉化為求叉乘if (k<eps || isZero(k) && dis(p[0], *c)>dis(p[0], *d)) return 1;return -1;
}double Graham(int n)
{int i,x=p[0].x,y=p[0].y;int mi=0;for( i=1;i<n;i++){if(p[i].x<x||(p[i].x==x&&p[i].y<y)){x=p[i].x;y=p[i].y;mi=i;}}point tmp=p[mi];p[mi]=p[0];p[0]=tmp;qsort(p+1, n-1, sizeof(point), cmp);p[n]=p[0];stack[0]=p[0];stack[1]=p[1];stack[2]=p[2];int top=2;for(i=3;i<=n;i++){while(crossProd(stack[top-1],stack[top],p[i])<eps &&top>=2) --top;stack[++top]=p[i];}double len=0;for(int i=0;i<top;i++) len+=dis(stack[i],stack[i+1]);return len;
}int main()
{int n;while(scanf("%d",&n),n){int i;for(i=0;i<n;i++){scanf("%lf %lf",&p[i].x,&p[i].y);}if(n==1) printf("0.00\n");else if(n==2) printf("%.2lf\n",dis(p[0],p[1]));elseprintf("%.2lf\n",Graham(n));}
}
總結
以上是生活随笔為你收集整理的hdu 1392 Surround the Trees的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
