题解 P4166 [SCOI2007]最大土地面积

· · 题解

先假设凸包的点数大于等于 4，问题比较一般化。

计算一个四边形的面积，我们可以考虑用一条对角线将四边形隔成两个三角形，分别计算两个三角形的面积。

所以我们可以考虑 O(n ^ 2) 枚举对角线。

现在想办法计算另外两个能将三角形面积取到最大的极值点，我们不妨继续利用类似求凸包最远点对的方法，由于面积的函数呈单峰函数，所以我们直接往后面用双指针扫就可以做这种情况了。

接着考虑当凸包的点数等于 3 时，我们是一个三角形包点，由于我们必选凸包上的点所以只剩下一个点的选择。

枚举剩下要选的点，得到所有可形成的凹四边形，需要取到所有凹四边形面积最大的凹四边形。

对于任意一个凹四边形可以分成三个含选择点的三角形，接下来只要看哪个三角形上，选择点是在三角形边上的右侧就知道哪个三角形不合法了，刨掉它即可算出当前凹四边形的面积。 

/*
找到每三点构成的最大三角形然后直接枚举？
*/
#include "bits/stdc++.h"
using namespace std;
const int Len = 2e3 + 5;
const double eps = 1e-3;
struct point
{
    double x,y;
    point(){x = y = 0.0;}
    point(double X,double Y){x = X , y = Y;}
    bool operator == (const point &Ano) const
    {
        return x == Ano.x && y == Ano.y;
    }
    point operator - (const point &Ano) const
    {return point(x - Ano.x , y - Ano.y);} 
    double operator ^ (const point &Ano) const
    {return x * Ano.y - y * Ano.x;}
    double operator * (const point &Ano) const
    {return x * Ano.x + y * Ano.y;}
}p[Len] , stk[Len << 1];
int top,n;
int idf(double x){if(fabs(x) < eps) return 0;if(x > 0) return 1;return -1; }
double mul(point p0,point p1,point p2){return (p1 - p0) ^ (p2 - p0);}
double dis(point a,point b){return ((b - a) * (b - a));}
bool cmp(point x,point y)
{
    double tmp = mul(p[1] , x , y);
    if(idf(tmp) > 0) return 1;
    if(idf(tmp) == 0 && dis(p[1] , x) < dis(p[1] , y)) return 1;
    return 0;
}
void Init()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++)
    {
        scanf("%lf %lf",&p[i].x,&p[i].y);
        if((p[i].y < p[1].y) || (p[i].y == p[1].y && p[i].x < p[1].x)) swap(p[i] , p[1]);
    }
}
void Find_Hull()
{
    sort(p + 2 , p + 1 + n , cmp);
    stk[top = 1] = p[1]; 
    for(int i = 2 ; i <= n ; i ++)
    {
        if(p[i - 1].x == p[i].x && p[i - 1].y == p[i].y) continue;
        while(top > 1 && idf(mul(stk[top - 1] , stk[top] , p[i])) <= 0) top --;
        stk[++ top] = p[i];
    }
    stk[top + 1] = p[1];
}
inline int Nxt(int x)
{
    if(x + 1 > top) return x + 1 - top;
    return x + 1;
}
int aside(point a,point b,point c)
{
    double mul = (b - a) ^ (c - a);
    if(mul > 0) return 1;
    if(mul < 0) return 0;
    double minx = min(a.x , b.x) , maxx = max(a.x , b.x) , miny = min(a.y , b.y) , maxy = max(a.y , b.y);
    return (minx <= c.x) && (c.x <= maxx) && (miny <= c.y) && (c.y <= maxy);
}
double Max_S()
{
    //if(top == 2) return dis(stk[1] , stk[2]);
    double ans = 0.0;
    if(top == 2) return ans;
    if(top == 3)
    {
        for(int i = 1 ; i <= n ; i ++)
        {
            if(p[i] == stk[1] || p[i] == stk[2] || p[i] == stk[3]) continue;
            double nowS = 0.0;
            nowS += fabs(mul(stk[1] , stk[2] , p[i]));
            nowS += fabs(mul(stk[1] , stk[3] , p[i]));
            nowS += fabs(mul(stk[2] , stk[3] , p[i]));
            if(!aside(p[i] , stk[1] , stk[2])) nowS -= fabs(mul(stk[1] , stk[2] , p[i]));
            if(!aside(p[i] , stk[1] , stk[3])) nowS -= fabs(mul(stk[1] , stk[3] , p[i]));
            if(!aside(p[i] , stk[2] , stk[3])) nowS -= fabs(mul(stk[2] , stk[3] , p[i]));
            ans = max(ans , nowS);
        }
    }
    else
    {
        for(int i = 1 ; i <= top ; i ++) 
        {
            int a = i , b = Nxt(a);
            for(int j = b ; j != i ; j = Nxt(j))
            {
                while(j != a && fabs(mul(stk[i] , stk[j] , stk[a])) < fabs(mul(stk[i] , stk[j] , stk[a + 1]))) a = Nxt(a);
                while(i != b && fabs(mul(stk[i] , stk[j] , stk[b])) < fabs(mul(stk[i] , stk[j] , stk[b + 1]))) b = Nxt(b);
                ans = max(ans , fabs(mul(stk[i] , stk[j] , stk[a])) + fabs(mul(stk[i] , stk[j] , stk[b]))); 
            }
        }   
    }

    return ans;
}
int main()
{
    Init();
    Find_Hull();
    printf("%.3f\n",Max_S() / 2.0); 
    return 0;
}