凸包(旋转卡壳)

计算几何模板

struct ConvexHull
{
    const static int __=1e5+5;

    point ch[__];int n;

    static bool cmp(const point &x,const point &y)
    {
        if(x.x==y.x)
            return x.y<y.y;
        return x.x<y.x;
    }

    point& operator[](int x){return ch[x];}

    void add(point &p,int lim)
    {
        while(n>=lim && ((p-ch[n-1])^(ch[n]-ch[n-1]))>0)
            --n;
        ch[++n].set(p.x,p.y);
    }

    ConvexHull() {clear();}

    void get_ConvexHull(point p[],int np)
    {
        sort(p+1,p+1+np,cmp);
        n=0;
        for(int i=1;i<=np;++i)
            add(p[i],2);
        for(int i=np-1,j=n;i>=1;--i)
            add(p[i],j+1);
        --n;
    }

    //周长(若凸包为直线需要除以2)
    double circumference()
    {
        ch[n+1]=ch[1];
        double res=0.0;
        for(int i=1;i<=n;++i)
            res+=line(ch[i],ch[i+1]).length();
        return res;
    }

    void print()
    {
        for(int i=1;i<=n;++i)
            printf("%.2f %.2f\n",(double)ch[i].x,(double)ch[i].y);
    }

    void clear(){n=0;}
}C;

旋转卡壳:

struct point
{
    ll x,y;
    point(ll x=0,ll y=0):
        x(x),y(y) {}
    friend ll operator*(const point& a,const point& b)
    {
        return a.x*b.y-a.y*b.x;
    }
};

point p[100005],tb[100005];

bool cmp(const point& a,const point& b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}

double cross(const point& st,const point& fir,const point& sec)
{
    double x1=fir.x-st.x,y1=fir.y-st.y;
    double x2=sec.x-st.x,y2=sec.y-st.y;
    return x1*y2-x2*y1;
}

point xl(const point& a,const point& b)//向量b->a
{
    return point(a.x-b.x,a.y-b.y);
}

int tubao(int n)
{
    sort(p+1,p+n+1,cmp);
    int m=0;
    for(int i=1; i<=n; i++)
    {
        while(m>1 && xl(p[i],tb[m-2])*xl(tb[m-1],tb[m-2])>=0)m--;
        tb[m++]=p[i];
    }
    int temp=m;
    for(int i=n-1; i>=1; i--)
    {
        while(m>temp && xl(p[i],tb[m-2])*xl(tb[m-1],tb[m-2])>=0)m--;
        tb[m++]=p[i];
    }
    if(n>1)m--;
//  for(int i=0;i<m;i++)
//      printf("p: %d %d\n",tb[i].x,tb[i].y);
    return m;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(p,0,sizeof(p));
        memset(tb,0,sizeof(tb));
        for(int i=1; i<=n; i++)
            scanf("%lld%lld",&p[i].x,&p[i].y);
        int m=tubao(n);
        tb[m]=tb[0];
        int x=2;
        ll ans=0;
        for(int i=0; i<=m-1; i++)
        {
            while(cross(tb[x],tb[i],tb[(i+1)%m])<
                  cross(tb[(x+1)%m],tb[i],tb[(i+1)%m]))
                x=(x+1)%m;
            ans=max(ans,(tb[x].x-tb[i].x)*(tb[x].x-tb[i].x)
                    +(tb[x].y-tb[i].y)*(tb[x].y-tb[i].y));
            ans=max(ans,(tb[x].x-tb[(i+1)%m].x)*(tb[x].x-tb[(i+1)%m].x)
                    +(tb[x].y-tb[(i+1)%m].y)*(tb[x].y-tb[(i+1)%m].y));
        }
        printf("%lld\n",ans);
    }
    return 0;
}

题目链接:面积最大的三角形

旋转卡壳:

struct point
{
    ll x,y;
    point(ll x=0,ll y=0):
        x(x),y(y) {}
    friend ll operator*(const point& a,const point& b)
    {
        return a.x*b.y-a.y*b.x;
    }
};

point p[50005],tb[50005];

bool cmp(const point& a,const point& b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}

double cross(const point& st,const point& fir,const point& sec)
{
    double x1=fir.x-st.x,y1=fir.y-st.y;
    double x2=sec.x-st.x,y2=sec.y-st.y;
    return x1*y2-x2*y1;
}

point xl(const point& a,const point& b)//向量b->a
{
    return point(a.x-b.x,a.y-b.y);
}

int tubao(int n)
{
    sort(p+1,p+n+1,cmp);
    int m=0;
    for(int i=1; i<=n; i++)
    {
        while(m>1 && xl(p[i],tb[m-2])*xl(tb[m-1],tb[m-2])>=0)m--;
        tb[m++]=p[i];
    }
    int temp=m;
    for(int i=n-1; i>=1; i--)
    {
        while(m>temp && xl(p[i],tb[m-2])*xl(tb[m-1],tb[m-2])>=0)m--;
        tb[m++]=p[i];
    }
    if(n>1)m--;
// for(int i=0;i<m;i++)
    //    printf("p: %lld %lld\n",tb[i].x,tb[i].y);
    return m;
}

int main()
{
    int n;
    while(~scanf("%d",&n) && ~n)
    {
        memset(p,0,sizeof(p));
        memset(tb,0,sizeof(tb));
        for(int i=1; i<=n; i++)
            scanf("%lld%lld",&p[i].x,&p[i].y);
        int m=tubao(n);
        tb[m]=tb[0];
        double ans=0;
        int fir=1,sec=2;
        for(int i=0; i<=m-1; i++)
        {
            while(1)
            {
                while(cross(tb[i],tb[fir],tb[sec])<cross(tb[i],tb[fir],tb[(sec+1)%m]))
                    sec=(sec+1)%m;
                while(cross(tb[i],tb[fir],tb[sec])<cross(tb[i],tb[(fir+1)%m],tb[sec]))
                    fir=(fir+1)%m;
                if((cross(tb[i],tb[fir],tb[sec])>=cross(tb[i],tb[(fir+1)%m],tb[sec]))
                &&(cross(tb[i],tb[fir],tb[sec])>=cross(tb[i],tb[fir],tb[(sec+1)%m])))
                    break;
            }
            ans=max(ans,fabs(cross(tb[i],tb[fir],tb[sec]))/2.0);
        }
        printf("%.2f\n",ans);
    }
    return 0;
}