题目：

3

3 4

2 6

3 7

6

2 6

3 9

2 0

8 0

6 6

7 7

1.50

27.00

题目分析：

凸包的简单应用，在n个点中找到3个点,它们所形成的三角形面积最大。

这道题一般来说有两种思路：

1）直接暴力。这肯定会TLE，由于n的数据范围都在50000左右了。

2）先求凸包。

然后再在凸包上去找这三个点。这种话，数据规模就要小非常多了。事实证明，能形成最大三角形的

这三个点也一定在凸包上。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

/**

 * 求n个点中随意三个点所形成的三角形的最大面积。

 * 1)直接暴力。

肯定会TLE。

由于n都是50000多了。

*

 * 2)所形成的最大三角形的三个点肯定在凸包上。

在凸包上找这三个点

 * 将问题转化成:

 * 在凸包上求三个点所形成的三角形的面积最大..

 */

const double epsi = 1e-8;

const double pi = acos(-1.0);

const int maxn = 50001;

struct PPoint{//结构体尽量不要定义成Point这种,easy和C/C++本身中的变量同名

	double x;

	double y;

	PPoint(double _x = 0,double _y = 0):x(_x),y(_y){

	}

	PPoint operator - (const PPoint& op2) const{

		return PPoint(x - op2.x,y - op2.y);

	}

	double operator^(const PPoint &op2)const{

		return x*op2.y - y*op2.x;

	}

};

inline int sign(const double &x){

	if(x > epsi){

		return 1;

	}

	if(x < -epsi){

		return -1;

	}

	return 0;

}

inline double sqr(const double &x){

	return  x*x;

}

inline double mul(const PPoint& p0,const PPoint& p1,const PPoint& p2){

	return (p1 - p0)^(p2 - p0);

}

inline double dis2(const PPoint &p0,const PPoint &p1){

	return sqr(p0.x - p1.x) + sqr(p0.y - p1.y);

}

inline double dis(const PPoint& p0,const PPoint& p1){

	return sqrt(dis2(p0,p1));

}

int n;

PPoint p[maxn];

PPoint convex_hull_p0;

inline bool convex_hull_cmp(const PPoint& a,const PPoint& b){

	return sign(mul(convex_hull_p0,a,b)>0)|| (sign(mul(convex_hull_p0,a,b)) == 0 && dis2(convex_hull_p0,a) < dis2(convex_hull_p0,b));

}

int convex_hull(PPoint* a,int n,PPoint* b){

	int i;

	for(i = 1 ; i < n ; ++i){

		if(sign(a[i].x - a[0].x) < 0 || (sign(a[i].x - a[0].x) == 0 && sign(a[i].y - a[0].y) < 0)){

			swap(a[i],a[0]);

		}

	}

	convex_hull_p0 = a[0];//这两行代码不要顺序调换了..否则会WA

	sort(a,a+n,convex_hull_cmp);

	b[0] = a[0];

	b[1] = a[1];

	int newn = 2;

	for(i = 2 ; i < n ; ++i){

		while(newn > 1 && sign(mul(b[newn-1],b[newn-2],a[i])) >= 0){

			newn--;

		}

		b[newn++] = a[i];

	}

	return newn;

}

/**

 * 有一个三角形的三个点来计算这个三角形的面积

 */

double crossProd(PPoint A, PPoint B, PPoint C) {

    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);

}

int main(){

	while(scanf("%d",&n)!=EOF){

		int i;

		for(i = 0 ; i < n ; ++i){

			scanf("%lf %lf",&p[i].x,&p[i].y);

		}

		n = convex_hull(p,n,p);

		p[n] = p[0];

		double max_ans = -1;

		int j;

		int k;

		for(i = 0 ; i < n ; ++i){

			for(j = i+1 ; j < n ; ++j){

				for(k = j+1 ; k <= n ; ++k){

					double ans = fabs(crossProd(p[i],p[j],p[k]))/2;

					if(max_ans < ans){

						max_ans = ans;

					}

				}

			}

		}

		printf("%.2lf\n",max_ans);

	}

	return 0;

}