【简单凸包】LightOJ 1203 Guarding Bananas

分类：计算几何

lightoj凸包

【简单凸包】LightOJ 1203 Guarding Bananas题目链接：LightOJ 1203 Guarding Bananas题目大意

构造凸包，求凸包夹角的最小值

笔者的第一道凸包题目，，发现Kuangbin的计算几何模板的一个最大缺陷：结构体太长，大空间开不下QAQ

凸包，我的理解是包含已知点集的最小凸集，二维凸包自然可以理解为包含所有点的最小凸多边形。

现在代码的逼格越来越高了~(≧▽≦)/~啦啦啦！

说一下思路①Graham’s Scan法构建凸包，时间复杂度O(nlogn)②遍历凸包中所有顶点，利用余弦定理求出所有夹角并取出其中的最小值参考代码/*==================================================*\| Graham求凸包 O(N * logN)| CALL: nr = graham(pnt, int n, res); res[]为凸包点集;\*==================================================*/;const int _max = 1e5 + 10;const double PI = acos(-1);int n;struct point{double x,y;}p[_max],res[_max];bool mult(point sp,point ep,point op){ return (sp.x – op.x) * (ep.y – op.y)>= (ep.x – op.x) * (sp.y – op.y);}bool operator < (const point &l, const point &r){ return l.y < r.y ||(l.y == r.y && l.x < r.x);}int graham(point pnt[],int n, point res[]){//构造凸包 int i,len ,k = 0,top = 1; sort(pnt,pnt+n); if(n == 0)return 0; res[0] = pnt[0]; if(n == 1)return 1; res[1] = pnt[1]; if(n == 2)return 2; res[2] = pnt[2]; for(int i =2; i < n; ++ i){while(top && mult(pnt[i],res[top],res[top-1]))top–;res[++top] = pnt[i]; } len = top; res[++top] = pnt[n – 2]; for(i = n – 3; i >= 0; — i){while(top!=len && mult(pnt[i],res[top],res[top-1]))top–;res[++top] = pnt[i]; } return top;//返回凸包中点的个数}double len(point A,point B){//返回向量AB的模 return hypot(A.x-B.x,A.y-B.y);}double dot(point A,point B,point C){//点乘 return (C.x-A.x)*(B.x-A.x)+(C.y-A.y)*(B.y-A.y);}(dot(A,B,C)/len(A,B)/len(A,C));}; double ans = 2 * PI; res[n] = res[0];res[n+1] = res[1]; for(int i = 1; i<= n; ++ i){ans = min(ans,get(res[i],res[i+1],res[i-1])); } return ans/PI*180;}int main(){ #ifndef ONLINE_JUDGE freopen(“input.txt”,”r”,stdin); #endif // ONLINE_JUDGE int T;cin>>T;int cnt=1; while(T–){scanf(“%d”,&n);for(int i = 0; i < n; ++ i){scanf(“%lf%lf”,&p[i].x,&p[i].y);}n = graham(p,n,res);//构造凸包printf(“Case %d: “,cnt++);printf(“%.7f\n”,minangle()); } return 0;}

上一篇【线段树】hdu 1754 I Hate It下一篇【最小矩形面积覆盖：凸包+旋转卡壳】UVA 10173Smallest Bounding Rectangle

顶0踩0

人生有一半掌握在上帝那里，另一半攥在自己的手中。

相关文章：

你感兴趣的文章：

标签云：