Home > Database > Mysql Tutorial > body text

How to understand that the judgment point of xyz is within the convex hull template

坏嘻嘻
Release: 2018-09-15 09:44:50
Original
3583 people have browsed it

The content of this article is about how to understand the xyz judgment point in the convex hull template. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

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;
}
Copy after login

The above is the detailed content of How to understand that the judgment point of xyz is within the convex hull template. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template