CodeForces - 340B Maximal Area Quadrilateral

Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral.

Input

The first line contains integer n (4 ≤ n ≤ 300). Each of the next n lines contains two integers: xi, yi ( - 1000 ≤ xi, yi ≤ 1000) — the cartesian coordinates of ith special point. It is guaranteed that no three points are on the same line. It is guaranteed that no two points coincide.

Output

Output a single real number — the maximal area of a special quadrilateral. The answer will be considered correct if its absolute or relative error does't exceed 10 - 9.

Examples

Input

5
0 0
0 4
4 0
4 4
2 3

Output

16.000000

Note

In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is 4·4 = 16.

题意：输入一些点，找到4点组成的面积最大，没有别的要求，就是四边形面积，不管是凸的还是凹的。

题解：固定一条边，枚举所有的点，找到上三角形和下三角形的最大值，数据范围300，直接暴力。暴力过一切。。。。。上代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 400;
struct hh{
	double x,y;
}a[MAX];
double jisuan(hh a,hh b,hh c){//叉乘求面积
	double x1,y1,x2,y2;
	x1=b.x-a.x;
	y1=b.y-a.y;
	x2=c.x-a.x;
	y2=c.y-a.y;
	return (x1*y2-x2*y1)/2;
}
int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n;i++){
		cin >> a[i].x >> a[i].y;
	}
	double area,l,r;
	area=0;
	for (int i = 0; i < n;i++){
		for (int j = i+1;j < n;j++){
			l=r=0;
			for (int k = 0; k < n;k++){//点跟i，j对应的点重合没关系，因为重合面积为0，这里不能写j+1，否则缺失情况。画图看一下就好，很简单~~~
				double w=jisuan(a[i],a[j],a[k]);
				if(w>0&&w>l) l=w;//上三角形找最大值
				else if(w<0&&-w>r) r=-w;//下三角形找最大值	 
			}
			if(l+r>area&&l>0&&r>0) area=l+r;//需要判断能组成四边形，即需要l>0,r>0
		}
	}
	printf("%.6f\n",area);
	return 0;
}