hdu 1392 Surround the Trees 凸包模板题

发布时间:2016-12-11 6:30:13 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 1392 Surround the Trees 凸包模板题",主要涉及到hdu 1392 Surround the Trees 凸包模板题方面的内容,对于hdu 1392 Surround the Trees 凸包模板题感兴趣的同学可以参考一下。

#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std; const int maxn=111; struct node{ int x,y; }e[maxn],res[maxn]; int cmp(node a,node b) { if(a.x==b.x)return a.y<b.y; return a.x<b.x; } int cross(node a,node b,node c)//向量积 { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } int convex(int n) { sort(e,e+n,cmp); int m=0,i,j,k; //求得下凸包,逆时针 for(i=0;i<n;i++) { while(m>1&&cross(res[m-1],e[i],res[m-2])<=0)m--; res[m++]=e[i]; } k=m; //求得上凸包 for(i=n-2;i>=0;i--) { while(m>k&&cross(res[m-1],e[i],res[m-2])<=0)m--; res[m++]=e[i]; } if(n>1)m--;//起始点重复。 return m; } double segment(node a,node b) { return sqrt(1.0*(b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y)); } int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0)break; int i,j,k,x,y,m; for(i=0;i<n;i++) scanf("%d%d",&e[i].x,&e[i].y); m=convex(n); double ans=0; if(m==2){printf("%.2lf\n",segment(res[0],res[1]));continue;}// !! for(i=1;i<m;i++) ans+=segment(res[i],res[i-1]); ans+=segment(res[m-1],res[0]); printf("%.2lf\n",ans); } return 0; } /* 凸包模板题 水平序的Andrew算法,求凸包。时间复杂度O(n) 最大三角形的三个顶点必定在凸包上,枚举即可。 向量积:a×b=x1*y2-x2*y1;当a×b>0时b在a的逆时针方向,a×b<0时b在顺时针方向,a×b=0时共线 */

上一篇:Git错误non-fast-forward后的冲突解决
下一篇:SQL语句执行顺序

相关文章

相关评论