Heim  >  Artikel  >  Datenbank  >  Wie kann man verstehen, dass der Beurteilungspunkt von xyz innerhalb der konvexen Hüllenvorlage liegt?

Wie kann man verstehen, dass der Beurteilungspunkt von xyz innerhalb der konvexen Hüllenvorlage liegt?

坏嘻嘻
坏嘻嘻Original
2018-09-15 09:44:503559Durchsuche

Der Inhalt dieses Artikels befasst sich mit dem Verständnis des xyz-Beurteilungspunkts in der konvexen Rumpfvorlage. Ich hoffe, dass er für Sie hilfreich ist.

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;
}

Das obige ist der detaillierte Inhalt vonWie kann man verstehen, dass der Beurteilungspunkt von xyz innerhalb der konvexen Hüllenvorlage liegt?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn