您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
小编给大家分享一下怎么理解xyz的判断点在凸包内模板,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
int n,m,tot; struct point { double x,y; }p[100000],a[100000],ss; bool cmp(point A,point B) { if(A.x!=B.x) return A.x<B.x; return A.y<B.y; } point operator -(point A,point B) { point c; c.x=A.x-B.x; c.y=A.y-B.y; return c; } double cross(point A,point B) { return A.x*B.y-B.x*A.y; } void dopack() { tot=0; for(int i=1;i<=n;i++) { while(tot>1&&cross(p[tot-1]-p[tot-2],a[i]-p[tot-2])<=0)tot--; p[tot++]=a[i]; } int k=tot; for(int i=n-1;i>0;i--) { while(tot>k&&cross(p[tot-1]-p[tot-2],a[i]-p[tot-2])<=0)tot--; p[tot++]=a[i]; } if(n>1)tot--; } bool check(point A) { int l=1,r=tot-2,mid; while(l<=r) { mid=(l+r)>>1; double a1=cross(p[mid]-p[0],A-p[0]); double a2=cross(p[mid+1]-p[0],A-p[0]); if(a1>=0&&a2<=0) { if(cross(p[mid+1]-p[mid],A-p[mid])>=0)return true; return false; } else if(a1<0) { r=mid-1; } else { l=mid+1; } } return false; }
以上是怎么理解xyz的判断点在凸包内模板的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。