[摘要]本篇文章给大家带来的内容是关于如何理解xyz的判断点在凸包内模板，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。int n,m,tot;
struct point
{double ... 本篇文章给大家带来的内容是关于如何理解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的判断点在凸包内模板的详细内容，更多请关注php中文网其它相关文章！
学习教程快速掌握从入门到精通的SQL知识。
|