Problem Description
老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角形拥有的面积最大。
Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。
Input
输入数据包含多组测试用例，每个测试用例的第一行包含一个整数n，表示一共有n个互不相同的点，接下来的n行每行包含2个整数xi,yi，表示平面上第i个点的x与y坐标。你可以认为：3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.
Output
对于每一组测试数据，请输出构成的最大的三角形的面积，结果保留两位小数。
每组输出占一行。
Sample Input
3
3 4
2 6
3 7
6
2 6
3 9
2 0
8 0
6 6
7 7
Sample Output
1.50
27.00
计算几何-凸包（GrahamScan）
得到最左下的点,将其他点按逆时针顺序排序,然后开始扫描,如果有ccw(stk[tt-1],stk[tt],s[i])为顺时针则删去栈首
找到凸包集合后直接枚举三角形即可
注意vector的push_back可能会慢,用resize的操作可以提高速度
点击查看代码
#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
const double eps=1e-10;
const int COUNTER_CLOCKWISE=1;
const int CLOCKWISE=-1;
const int ONLINE_FRONT=2;
const int ONLINE_BACK=-2;
const int ON_SEGMENT=0;
int xx,yy;
class Point
{
public:
double x,y;
Point(double x=0,double y=0): x(x),y(y) {}
double abs() {return sqrt(norm());}
double norm() {return x*x+y*y;}
Point operator + (const Point &p) const
{
return Point(x+p.x,y+p.y);
}
Point operator - (const Point &p) const
{
return Point(x-p.x,y-p.y);
}
bool operator == (const Point &p) const
{
return fabs(x-p.x)<eps&&fabs(y-p.y)<eps;
}
};
typedef Point Vector;
typedef vector<Point> Polygon;
double dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y;
}
double cross(Vector a,Vector b)
{
return a.x*b.y-a.y*b.x;
}
bool cmp(Point a,Point b)
{
Point t(xx,yy);
Vector p1=a-t,p2=b-t;
int m=cross(p1,p2);
if(m>0) return 1;
else if(m==0) return p1.norm()<p2.norm();
else return 0;
}
int ccw(Point p0,Point p1,Point p2)
{
Vector a=p1-p0;
Vector b=p2-p0;
if(cross(a,b)>eps) return COUNTER_CLOCKWISE;
if(cross(a,b)<-eps) return CLOCKWISE;
if(dot(a,b)<-eps) return ONLINE_BACK;
if(a.norm()>b.norm()) return ONLINE_FRONT;
return ON_SEGMENT;
}
double S(Polygon s)
{
double res=0;
int len=s.size();
for(int i=0;i<len;++i)
{
res+=cross(s[i],s[(i+1)%len]);
}
return fabs(res)/2;
}
Polygon GrahamScan(Polygon s)
{
Polygon u;
int len=s.size();
if(len<=3) return s;
sort(s.begin()+1,s.end(),cmp);
u.resize(len+1);
int tt=0;
u[0]=s[0],u[++tt]=s[1];
for(int i=2;i<len;++i)
{
while(tt>=1&&ccw(u[tt-1],u[tt],s[i])==CLOCKWISE) tt--;
//cout<<u[tt].x<<' '<<u[tt].y<<'\n';
u[++tt]=s[i];
}
u.resize(tt+1);
return u;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
Polygon P;
P.resize(n);
xx=0x3f3f3f3f;
yy=0x3f3f3f3f;
int mini;
for(int i=0;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
P[i]=Point(x,y);
if(y<=yy)
{
if(y<yy) yy=y,xx=x,mini=i;
else if(x<xx) xx=x,mini=i;
}
}
swap(P[0],P[mini]);
//cout<<P[0].x<<' '<<P[0].y<<"/"<<endl;
auto A=GrahamScan(P);
//for(auto x:A) cout<<x.x<<' '<<x.y<<'\n';
int len=A.size();
double ans=0;
for(int i=0;i<len;++i)
for(int j=i+1;j<len;++j)
for(int k=j+1;k<len;++k)
{
Polygon P1(3);
P1[0]=A[i];
P1[1]=A[j];
P1[2]=A[k];
ans=max(ans,S(P1));
}
printf("%.2lf\n",ans);
}
}