USACO Section 5.1 Fencing the Cows - 凸包模板题~~

网友投稿 244 2022-08-25

USACO Section 5.1 Fencing the Cows - 凸包模板题~~

USACO本节开头的TXT将得就是凸包的求法~~

题目的原意是给出N个点...问最少要用多长的栅栏才能将所有点都围起来..

求出平面中这些点的凸包...凸包的周长就是解..很好想到的..

我是用Graham写的...好久没写凸包了...很不熟练...调了一晚上才出来...再次总结一下Graham求凸包的顺序:

1 . 找出最左下方的点...并将其挪到point [ 0 ] 方便操作...

2 . 以这个点为原点求出其他所有点的极角,并按极角对除左下方的所有点重新排序..( 开始我想当极角相等时需不需要按到左下点的距离进行二次判断,发现没有必要..只要按极角排序就可以了 )

3 . 可以肯定地是极角最大的点和最小的点肯定在凸包上..用一个栈..将重新排序后的0,1先依次压入栈...

4 . 从point [ 2 ] 开始扫到 point [ n ] 每次的目的是将这个点加到凸包上..若加不上去 ( 非向左拐 )..就弹栈,直到加上这个点是向左拐的...

Program:

/* ID: zzyzzy12 LANG: C++ TASK: fc*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std;struct node1{ double x,y,alp; }point[10005];double dist(node1 a,node1 b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }bool cmp(node1 a,node1 b){ return a.alp-0.00001) return true; return false;}double Graham(){ int i,num,mystack[10005]; double ans=0; num=2; mystack[1]=0; mystack[2]=1; for (i=2;i<=n;i++) { while (!left(point[mystack[num-1]],point[mystack[num]],point[i])) num--; mystack[++num]=i; } mystack[num+1]=0; for (i=1;i<=num;i++) ans+=dist(point[mystack[i]],point[mystack[i+1]]); return ans; }int main() { freopen("fc.in","r",stdin); freopen("fc.out","w",stdout); int i; scanf("%d",&n); k=1; for (i=1;i<=n;i++) { scanf("%lf%lf",&point[i].x,&point[i].y); if (point[i].x

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：排序
上一篇:USACO Section 4.3 Letter Game - 简单枚举
下一篇:北京今年将新建100处足球场、篮球场等健身活动场所！（足球场 篮球场）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~