P0417

[SCOI2007]最大土地面积

[SCOI2007]最大土地面积

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

输入格式

第一行一个正整数 NN。

接下来 NN 行,每行两个数 x,yx, y,表示该点的横坐标和纵坐标。

输出格式

一行一个数,表示最大的多边形面积,答案精确到小数点后 33 位。

样例输入

5
0 0
1 0
1 1
0 1
0.5 0.5

样例输出

1.000

样例解释

取 (0,0)(0,0)、(1,0)(1,0)、(1,1)(1,1)、(0,1)(0,1) 这四个点,围成一个边长为 11 的正方形,面积为 1.0001.000,这是所有取法中面积最大的。

数据范围

  • n≤2000n\le 2000;
  • ∣x∣,∣y∣≤105|x|, |y|\le 10^5。

来源与许可

本题为 SCOI 2007 试题「最大土地面积」,题面与测试数据整理自 BZOJ 1069。

样例 1

输入

5
0 0
1 0
1 1
0 1
0.5 0.5

输出

1.000