题意：给N个点，求着N个点中选择三个联的最大的三角形面积！
注意精度：不然OJ上面会超时的
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
const double eps = 1e-8;
using namespace std;
struct point
{
int x,y;
} p[50005],res[50005];
int cross(point p0, point p1, point p2)//计算叉积
{
return(p1.x- p0.x) * (p2.y- p0.y) - (p1.y- p0.y) * (p2.x- p0.x);
}//顺时针扫描，判断大于0（方向改变）的加入凸包，然后回溯
double dist(point a,point b)//两点距离
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a, point b)//按照y小到大排序，y相等按照x小到大排序
{
return(a.y< b.y|| (a.y== b.y&& a.x< b.x));
}
int Graham(int n)//求凸包，返回凸包上顶点的个数
{
int len, top=1;
sort(p, p+ n, cmp);
res[0] = p[0];
res[1] = p[1];
for(int i=2; i< n; i++)
{
while(top&& cross(res[top], res[top-1], p[i])<=eps)top--;
res[++ top] = p[i];
}
len= top;
res[++ top] = p[n-2];
for(int i= n-3; i>=0; i--)
{
while(top!= len&& cross(res[top], res[top-1], p[i])<=eps)top--;//注意精度问题，不然会超时的
res[++ top] = p[i];
}
return top;
}
int main()
{
int n,top;
while(scanf("%d",&n)!=EOF)
{
double MAX=-1;
for(int i=0; i<n; i++)
scanf("%d%d", &p[i].x ,&p[i].y);
top=Graham(n);
for(int i=0; i<top-2; i++)
for(int j=i+1; j<top-1; j++)
for(int k=j+1; k<top; k++)
{
double ss=fabs(cross(res[i],res[j],res[k]));
if(ss>MAX) MAX=ss;//暴力利用叉积计算三角形的面积
}
printf("%.2f\n",MAX/2.0);
}
return 0;
}
另一个版本的凸包
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
const double eps = 1e-8;
using namespace std;
struct point
{
int x,y;
} p[50005],res[50005];
int cross(point p0, point p1, point p2)//计算叉积
{
return(p1.x- p0.x) * (p2.y- p0.y) - (p1.y- p0.y) * (p2.x- p0.x);
}//顺时针扫描，判断大于0（方向改变）的加入凸包，然后回溯
double dist(point a,point b)//两点距离
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a, point b)//极角排序，先用arctan()判断角大小，角度由小到大，然后用距离小到大排序
{
double t1 = atan2(a.y - p[0].y, a.x - p[0].x);
double t2 = atan2(b.y - p[0].y, b.x - p[0].x);
return t1>t2||(t1==t2&&dist(p[0],a)<dist(p[0],b));
}
int Graham(int n)//求凸包，返回凸包上顶点的个数
{
int len, top,tmp=0;
for(int i=1;i<n;i++)
if(p[tmp].y>p[i].y||(p[tmp].y==p[i].y&&p[tmp].x>p[i].x))
tmp=i;
swap(p[0],p[tmp]);//找出最左下角的点
sort(p+1, p+ n,cmp);
res[0] = p[0];
res[1] = p[1];
res[2] =p[2];
top=2;
for(int i=2; i<n; i++)
{
while(top>=2&& cross(res[top], res[top-1], p[i])<=eps)top--;
res[++ top] = p[i];
}//只用一次扫描
res[++top]=p[n-1];//完了要把最后一个点加上去
return top;
}
int main()
{
int n,top;
while(scanf("%d",&n)!=EOF)
{
double MAX=-1;
for(int i=0; i<n; i++)
scanf("%d%d", &p[i].x ,&p[i].y);
top=Graham(n);
for(int i=0; i<top-2; i++)
for(int j=i+1; j<top-1; j++)
for(int k=j+1; k<top; k++)
{
double ss=fabs(cross(res[i],res[j],res[k]));
if(ss>MAX) MAX=ss;//暴力利用叉积计算三角形的面积
}
printf("%.2f\n",MAX/2.0);
}
return 0;
}