「SCOI2007」最大土地面积

· · 题解

题目描述见原题。

原来以为洛谷上会有很多人发现 hack 点但实际上并没有……

要求平面最大组成的四边形面积，实际上和 Gym102460L 是一样的，但是由于原 SCOI 题面写的实在是太模糊，并没有说数据是否有重复的点（但是本题中好像不影响答案），所以还是看 Gym 的那道题描述好些。

首先根据调整法，可以证明最大四边形至少有三个点在凸包上，但是凸包大小有三种情况，下面分情况讨论：

凸包大小小于等于 2 时

当凸包大小小于等于 2，可以说明原来的所有点都是共线或共点的，易知答案为 0。

凸包大小等于 3 时

几乎网上所有题解都忽略了这点，但是 Gym 题目的样例中就能将这些代码卡掉。貌似题解区只有一个灰名用暴力+常数优化过了 hack……

考虑所有的点都在一个三角形范围内，这时答案应该是一个凹四边形，利用旋转卡壳是无法正确求解的。但是根据性质，我们仅需要枚举除构成凸包的三个点以外的点，计算大三角形面积减去由这个点和三角形三边之一组成的三角形面积最小者，得到的就是最终答案了。

凸包大小大于等于 4 时

仍然根据调整法，可知此时组成最大四边形的四个点一定全部位于凸包上，此时枚举这个四边形的对角线，利用旋转卡壳的方式求解分布在对角线两侧的最大三角形，两部分之并即为最大四边形。

总时间复杂度为 \mathcal{O}(n^2)，空间复杂度 \mathcal{O}(n)。

代码如下：

#include <bits/stdc++.h>
#define MAXN 2005
using namespace std;

const double eps=1e-8;

struct Point
{
    double x,y,i;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    Point operator - (const Point &p2)const{
        return Point(x-p2.x,y-p2.y);
    }
    bool operator < (const Point p)const{
        if (p.x!=x) return p.x>x;
        return p.y>y;
    }
    double operator * (const Point &p2) {
        return 1LL*x*p2.y-1LL*y*p2.x;
    }
};

int n;
Point p[MAXN],ch[MAXN];

int ConvexHull(Point *p,int n)
{
    sort(p,p+n);int m=0;
    for (int i=0;i<n;i++)
    {
        while (m>1&&(ch[m-1]-ch[m-2])*(p[i]-ch[m-2])<=eps) --m;
        ch[m++]=p[i];
    }
    int k=m;
    for (int i=n-2;~i;i--)
    {
        while (m>k&&(ch[m-1]-ch[m-2])*(p[i]-ch[m-2])<=eps) --m;
        ch[m++]=p[i];
    }
    if (n>1) --m;
    return m;
}

inline bool OK(Point a,Point b,Point c,Point d)
{
    double A=fabs((b-a)*(c-a));
    double B=fabs((b-a)*(d-a));
    return A<B;
}

inline void Rotating_Calipers(int m)
{
    double ans=0,now;
    if (m<=2) ans=0;
    else if (m==3)
    {
        now=~(1LL<<63);
        ans=abs((ch[0]-ch[2])*(ch[1]-ch[2]));
        for (int i=0;i<n;i++)
        {
            if (ch[0].i==p[i].i||ch[1].i==p[i].i||ch[2].i==p[i].i) continue;
            double s1=fabs((ch[0]-p[i])*(ch[1]-p[i]));
            double s2=fabs((ch[1]-p[i])*(ch[2]-p[i]));
            double s3=fabs((ch[2]-p[i])*(ch[0]-p[i]));
            now=min(min(now,s1),min(s2,s3));
        }
        if (now!=~(1LL<<63)) ans-=now;
        else ans=0;
    }
    else
    {
        for (int i=0;i<m;i++)
        {
            int x=(i+1)%m,y=(i+2)%m;
            for (int j=(i+2)%m;j!=i;(++j)%=m)
            {
                while (x!=j&&OK(ch[i],ch[j],ch[x],ch[x+1])) (++x)%=m;
                while (y!=i&&OK(ch[i],ch[j],ch[y],ch[y+1])) (++y)%=m;
                now=fabs((ch[x]-ch[i])*(ch[j]-ch[i]))+fabs((ch[y]-ch[i])*(ch[j]-ch[i]));
                if (now>ans) ans=now;
            }
        }
    }
    printf("%.3lf\n",ans/2.0);
    return ;
}

int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%lf %lf",&p[i].x,&p[i].y),p[i].i=i;
    Rotating_Calipers(ConvexHull(p,n));
    return 0;
}
/*
4
0 0
4 0
0 4
1 1
*/