Maison > base de données > tutoriel mysql > Comment comprendre que le point de jugement de xyz se trouve dans le modèle de coque convexe

Comment comprendre que le point de jugement de xyz se trouve dans le modèle de coque convexe

坏嘻嘻
Libérer: 2018-09-15 09:44:50
original
3585 Les gens l'ont consulté

Le contenu de cet article explique comment comprendre le point de jugement xyz dans le modèle de coque convexe. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

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;
}
Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal