最大三角形
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4015 Accepted Submission(s): 1433
Problem Description
老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角形拥有的面积最大。
Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。
Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。
Input
输入数据包含多组测试用例，每个测试用例的第一行包含一个整数n，表示一共有n个互不相同的点，接下来的n行每行包含2个整数xi,yi，表示平面上第i个点的x与y坐标。你可以认为：3
<= n <= 50000 而且 -10000 <= xi, yi <= 10000.
<= 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
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
27.00
Author
Eddy
代码：
//最大三角形的顶点一定是凸包的顶点，先求凸包再三重循环用向量算最大的三角形面积。刚开始以为这样会超时竟然没有
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,top;
struct nod
{
double x,y;
}p[],que[];
int xy(nod p0)
{
p0.x-=p[].x;
p0.y-=p[].y;
if(p0.x>=&&p[].y>=) return ;
if(p[].x<=&&p[].y>) return ;
if(p[].x<&&p[].y<=) return ;
if(p[].x>=&&p[].y<) return ;
}
double chaji(nod p0,nod p1,nod p2)
{
return ((p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x));
}
bool cmp(nod p1,nod p2)
{
int L1=xy(p1),L2=xy(p2);
if(L1==L2)
{
double tem=chaji(p[],p1,p2);
if(tem>) return ;
if(tem<) return ;
if(tem==)
return p1.x<p2.x;
}
else return L1<L2;
}
void tubao()
{
top=;
que[top].x=p[].x;que[top++].y=p[].y;
que[top].x=p[].x;que[top++].y=p[].y;
que[top].x=p[].x;que[top].y=p[].y;
for(int i=;i<=n;i++)
{
while(chaji(que[top-],que[top],p[i])<=)
top--;
que[++top].x=p[i].x;
que[top].y=p[i].y;
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
double Minx=,Miny=;
int Mini;
for(int i=;i<n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i].y<Miny)
{
Miny=p[i].y;
Minx=p[i].x;
Mini=i;
}
else if(p[i].y==Miny&&p[i].x<Minx)
{
Minx=p[i].x;
Mini=i;
}
}
if(n==||n==)
{
printf("0.00\n");
continue;
}
double tem=p[].x;
p[].x=p[Mini].x;
p[Mini].x=tem;
tem=p[].y;
p[].y=p[Mini].y;
p[Mini].y=tem;
sort(p+,p+n,cmp);
p[n].x=p[].x;p[n].y=p[].y;
tubao();
double ans=0.0;
for(int i=;i<=top-;i++)
for(int j=i+;j<=top-;j++)
for(int k=j+;k<=top;k++)
{
ans=max(fabs(chaji(que[i],que[j],que[k])),ans);
}
printf("%.2lf\n",ans/);
}
return ;
}