首先,我们知道,满足条件的三角形一定在凸包上,所以我们先求出凸包
然后,用旋转卡壳法走一遍即可
最后,吐槽一下POJ的评测机,G++那货能用?!
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=50005;
const double eps=1e-8;
struct Point{int x,y;}P[maxn],C[maxn];
int tchullp,n;
bool cross(Point a,Point b,Point op)//向量叉乘
{
return (a.x-op.x)*(b.y-op.y)>=(a.y-op.y)*(b.x-op.x);
}
int area(Point a,Point b,Point c)
{
return abs((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
}
bool comp(Point a,Point b)
{
return (a.y<b.y)||(a.y==b.y&&a.x<b.x);
}
int Chull()
{
int len,top=1;
sort(&P[0],&P[n],comp);
if (n==0) return 0;
C[0]=P[0];
if (n==1) return 1;
C[1]=P[1];
if (n==2) return 2;
C[2]=P[2];
for (int i=2;i<n;i++)
{
while (top&&cross(P[i],C[top],C[top-1]))
top--;
C[++top]=P[i];
}
len=top;
C[++top]=P[n-2];
for (int i=n-3;i>=0;i--)
{
while (len!=top&&cross(P[i],C[top],C[top-1]))
top--;
C[++top]=P[i];
}
return top;
}
double solve()
{
int ans=0;
int p1,p2=1,p3=2,m=Chull();
C[m]=C[0];
for (p1=0;p1<m;p1++)
{
while (area(C[p1],C[p2],C[(p3+1)%m])>area(C[p1],C[p2],C[p3]))
p3=(p3+1)%m;
ans=max(ans,area(C[p1],C[p2],C[p3]));
while (area(C[p1],C[(p2+1)%m],C[p3])>area(C[p1],C[p2],C[p3]))
p2=(p2+1)%m;
ans=max(ans,area(C[p1],C[p2],C[p3]));
}
return ans*0.5;
}
bool Main()
{
if (scanf("%d",&n)!=1)
return false;
if (n==-1)
return false;
for (int i=0;i<n;i++)
scanf("%d%d",&P[i].x,&P[i].y);
printf("%.2lf\n",solve());
return true;
}
int main()
{
while (Main());
return 0;
}