Game of Taking Stones && POJ1259 /// 最大空凸包 几何+DP

题目大意：

给定n个点 求出这n个点中最大空凸包的面积

只放个模板 一份模板过两题（滑稽

这个讲解够详细了 https://blog.csdn.net/nyroro/article/details/45268767

#include <stdio.h>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const double eps=1e-;

double add(double a,double b) {

    if(abs(a+b)<eps*(abs(a)+abs(b))) return ;

    return a+b;

} // 考虑误差

int dcmp(double x) {

    if(abs(x)<eps) return ;

    else return x< ? -:;

}

struct P {

    double x,y;

    P(){};

    P(double _x,double _y):x(_x),y(_y){}

    P operator -(P p) { return P(add(x,-p.x),add(y,-p.y)); };

    P operator +(P p) { return P(add(x,p.x),add(y,p.y)); };

    P operator *(double d) { return P(x*d,y*d); };

    double dot(P p) { return add(x*p.x,y*p.y); }; // 点积为0垂直

    double det(P p) { return add(x*p.y,-y*p.x); }; // 叉积为0平行

    void scf() { scanf("%lf%lf",&x,&y); }

}pa[], p[], O;

double lenV(P v) { return sqrt(v.dot(v)); }

bool cmp(P a,P b) {

    int f=dcmp((a-O).det(b-O));

    if(f==) return lenV(a-O)<lenV(b-O);

    return f>;

}

double dp[][], ans;

void MEP(int n) {

    sort(p,p+n,cmp);

    memset(dp,,sizeof(dp));

    for(int i=;i<n;i++) { // O-i 始终作为以st开始的凸包顺时针的第一条边

        int j=i-;

        while(j>= && dcmp((p[i]-O).det(p[j]-O))==) j--;

        // i-j 作为凸包的第二条边

        bool flag=(j==i-);

        while(j>=) {

            int k=j-;

            while(k>= && dcmp((p[i]-p[k]).det(p[j]-p[k]))>) k--;

            // 找到能作为凸包右下的一点的 k

            double area=abs((p[i]-O).det(p[j]-O))/2.0;

            if(k>=) area+=dp[j][k]; // 已求得的jk的MEP + 三角形Oij

            if(flag) dp[i][j]=area; /// j!=i-1时不更新dp数组

            /** 虽然对当前的凸包来说只是边界点没影响

                但是之后其他凸包需利用当前dp[i][j]时

                这些边界点会被包含在凸包内 */

            ans=max(ans,area);

            j=k;

        }

        if(flag)

            for(int j=;j<i;j++)

                dp[i][j]=max(dp[i][j],dp[i][j-]);

    }

}

int main()

{

    int t; scanf("%d",&t);

    while(t--) {

        int n; scanf("%d",&n);

        ans=;

        for(int i=;i<n;i++) pa[i].scf();

        for(int i=;i<n;i++) {

            O=pa[i];

            int c=;

            for(int j=;j<n;j++)

                if(pa[j].y>pa[i].y || dcmp(pa[j].y-pa[i].y)==&&pa[j].x>pa[i].x)

                    p[c++]=pa[j]; // 取O右上角的点

            MEP(c); //printf("%.1f\n",ans);

        }

        printf("%.1f\n",ans);

    }

    return ;

}