wuvin

Description

　　在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。

Input

　　第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

Output

　　最大的多边形面积，答案精确到小数点后3位。

Sample Input

5
0 0
1 0
1 1
0 1
0.5 0.5

Sample Output

1.000

HINT

数据范围 $n \le 2000 , |x|,|y| \le 100000$

今天上午考到这个原题，比较懒不想讨论凹四边形就写了个n^2logn，就T飞了，YZ和LCR的n^2由于常数大也T了。（测评机。。。）

三角形最大面积可以$O(n)$,所以花了半小时尝试推广到四边形，但始终没有成功，正确性很玄学啊。不过途中不小心搞出了另外一种$O(n)$的做法。

最大面积的四边形首先求个凸包不用说，nlogn。这是最大的复杂度了，后面就$O(n)$了。如果是凹的，那么凸包上一定只有三个点，另外一个枚举就是了$O(n)$。接下来是凸的情况。

先分析答案，有

推论一

最大面积四边形一定由两个对踵点对组成，不然就可以通过固定一条对角线改变一个点来扩大面积。

快省选滚粗了，来总结一下计算几何

计算几何是著名的口上A着快，写出来各种拿不到分，大坑小坑满天飞（做过的所有计算几何题只有两道1A了。所有计算几何几乎没法调试，没法对拍）。

所以在这里总结一下类型，先从基础讲起。信息学的几何和数学的几何有很大不同，由于有强大的计算能力所以一般直接爆算就是了，什么梅尼劳斯、费马点之类的公式完全用不上，暴力不解释。由于要解析几何，使用向量特别多，比如空间中一条直线，能用向量两点式就不用y=kx+b，为什么？k计算时会爆啊inf...,暴了就WA了。

向量的使用有极大的优势，可以不用区分象限什么的，面积叉积就好了，由于有了向量，什么距离面积都可以是负的，极大地统一了公式尽量免去了分类讨论与细节。

叉积

不支持交换律，A×B=a.x*b.y-b.x*a.y,就是由ABO所形成的三角形的面积的两倍（B在OA左侧为正，反之为负），至于证明。。。网上多的是。用来判断直线与点的位置关系用得最多。比如poj2318。用来求面积也有，比如bzoj1132。

极角

也就是向量与X轴正方向的夹角，这个可比数学好用多了，比如两角之和的cos值怎么求？和角公式？直接暴力atan2、acos、asin求出角度相减就是，然后再求一个cos，这时终于感到cmath库的强大了。例：bzoj1419.

向量旋转

可以如上方所述暴力，但暴力较慢，如果旋转操作特别多的话还是手推和差角公式转一转。练习题目poj3845。还有一道旋转玄学bzoj3707。(顺带附上一句bzoj3707的方法在有三点共线的情况下是错的别问我是怎么知道的，不过此题不影响，反正是0，只是这个方法不能用来求最大三角形面积。)

直线相交

向量两点式配合面积倒一倒来求交点还是很兹糍的，草稿纸上手玩一下就好了，不过要考虑到特殊情况才行。比如这几种情况

inline point get_inter(const seg &a,const seg &b){
    long double p1=-cross(dec(a.b,a.a),dec(b.b,a.a));
    long double p2=cross(dec(a.b,a.a),dec(b.a