本文摘自PHP中文网,作者坏嘻嘻,侵删。
本篇文章给大家带来的内容是关于如何理解xyz的判断点在凸包内模板,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | 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的判断点在凸包内模板的详细内容,更多文章请关注木庄网络博客!
相关阅读 >>
从以下几个方面来处理,mysql主从复制不一致的问题
详解mysql中order by多字段排序规则
mysql当前时间怎么表示
mysql触发器基本用法详解【创建、查看、删除等】
怎样使用mysql命令行修改mysql登录密码
mysql数据库触发器使用教程
mysql创建函数出错如何解决
mysql 聚合函数用法是什么
mysql5.7以上版本配置my.ini的详细步骤
mysql查询进阶操作从函数到表连接的使用
更多相关阅读请进入《判断点》频道 >>
机械工业出版社
本书主要讲述了数据模型、基于对象的数据库和XML、数据存储和查询、事务管理、体系结构等方面的内容。
转载请注明出处:木庄网络博客 » 如何理解xyz的判断点在凸包内模板