首先我们很容易看出 \(O(n^4)\) 是过不了的,所以我们考虑 \(O(n^3)\)
很明显,我们可以先用 \(O(n^2)\) 的复杂度枚举一条线段,然后再花 \(O(n)\) 的时间枚举其余所有点,然后我们可以用海伦公式算出这个三角形的面积,这样是为了让我们用两个三角形加起来的和凑成一个四边形,然后我们可以算一个一次函数,看这个三角形在这条线段的左侧还是右侧。再统计完左右两边三角形的最大值后相加,得出这条线段能得到的最大值,然后和答案比较。最后输出即可.
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-') f=0;c=getchar();}
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?x:-x;
}
struct node{double x,y;}a[305];
int n;
double s,s1,s2,k,b;
double dis(node x,node y){return sqrt(abs(x.x-y.x)*abs(x.x-y.x)+abs(x.y-y.y)*abs(x.y-y.y));}
double helen(node x,node y,node z)
{
double a=dis(x,y),b=dis(y,z),c=dis(x,z);
double p=(a+b+c)/2;
return sqrt(p*(p-a)*(p-b)*(p-c));
}
inline double max(double x,double y){return x>y?x:y;}
double ans;
signed main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
s1=s2=0;
for(int l=1;l<=n;l++)
{
if(l==i || l==j) continue;
s=helen(a[i],a[j],a[l]);
k=10000;
if(a[i].y!=a[j].y) k=(a[i].y-a[j].y)/(a[i].x-a[j].x);
b=a[i].y-a[i].x*k;
if(k==10000)
{
if(a[l].y>a[i].y) s1=max(s1,s);
else s2=max(s2,s);
}
else if(k==0)
{
if(a[l].x<a[i].x) s1=max(s1,s);
else s2=max(s2,s);
}
else
{
if(k<0)
{
if(a[l].y<k*a[l].x+b) s1=max(s1,s);
else s2=max(s2,s);
}
else
{
if(a[l].y>k*a[l].x+b) s1=max(s1,s);
else s2=max(s2,s);
}
}
}
if(s1 && s2) ans=max(ans,s1+s2);
}
}
printf("%.6lf",ans);
return 0;
}