可以发现，最小的三角形一定是贴在原多边形边上的，否则原来的就不是凸多边形了。我们可以枚举大三角形作为多边形对角线的一条边，在一边用旋转卡壳维护最远点，另外一边维护最小的三角形，复杂度 O(n3) 。 注意这题既卡精度又卡常数。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define LL long long const int maxn=5010; const LL oo=1e17; struct Vector { LL x,y; void rd() { scanf("%lld%lld",&x,&y); } Vector operator + (const Vector &v) const { return (Vector){x+v.x,y+v.y}; } Vector operator - (const Vector &v) const { return (Vector){x-v.x,y-v.y}; } }a[maxn]; typedef Vector Point; LL dot(Vector v,Vector u) { return v.x*u.x+v.y*u.y; } LL cross(Vector v,Vector u) { return v.x*u.y-v.y*u.x; } LL size(int x,int y,int z) { return abs(cross(a[x]-a[y],a[z]-a[y])); } int n,next[maxn],pre[maxn]; LL f[maxn]; int main() { int i,j,x; LL mn,ans=0; scanf("%d",&n); for (i=0;i<n;i++) a[i].rd(); for (int i=0;i<n;i++) { pre[i]=(i-1+n)%n; next[i]=(i+1)%n; f[i]=size(i,pre[i],next[i]); } for (i=0;i<n;i++) for (j=next[next[i]],x=next[j],mn=oo;next[j]!=i;j=next[j]) { mn=min(mn,f[pre[j]]); while (size(i,j,next[x])>size(i,j,x)) x=next[x]; ans=max(ans,size(i,j,x)-mn); } printf("%lld",ans/2); printf("%s\n",ans%2?".5":".0"); }