题目大意：
给定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-8; double add(double a,double b) { if(abs(a+b)<eps*(abs(a)+abs(b))) return 0; return a+b; } // 考虑误差 int dcmp(double x) { if(abs(x)<eps) return 0; else return x<0 ? -1:1; } 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[105], p[105], 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==0) return lenV(a-O)<lenV(b-O); return f>0; } double dp[105][105], ans; void MEP(int n) { sort(p,p+n,cmp); memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) { // O-i 始终作为以st开始的凸包顺时针的第一条边 int j=i-1; while(j>=0 && dcmp((p[i]-O).det(p[j]-O))==0) j--; // i-j 作为凸包的第二条边 bool flag=(j==i-1); while(j>=0) { int k=j-1; while(k>=0 && dcmp((p[i]-p[k]).det(p[j]-p[k]))>0) k--; // 找到能作为凸包右下的一点的 k double area=abs((p[i]-O).det(p[j]-O))/2.0; if(k>=0) 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=1;j<i;j++) dp[i][j]=max(dp[i][j],dp[i][j-1]); } } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); ans=0; for(int i=0;i<n;i++) pa[i].scf(); for(int i=0;i<n;i++) { O=pa[i]; int c=0; for(int j=0;j<n;j++) if(pa[j].y>pa[i].y || dcmp(pa[j].y-pa[i].y)==0&&pa[j].x>pa[i].x) p[c++]=pa[j]; // 取O右上角的点 MEP(c); //printf("%.1f ",ans); } printf("%.1f ",ans); } return 0; }