← 返回题目列表

Codeforces · 340/B

B. 最大面积四边形

中文机器翻译题面 查看原题

Iahub 在笛卡尔平面上绘制了一组 n 个点,他称之为“特殊点”。四边形是没有自相交的简单多边形,具有四个边(也称为边)和四个顶点(也称为角)。请注意,四边形不一定是凸的。特殊四边形是在一组特殊点中具有所有四个顶点的四边形。给定一组特殊点,请计算特殊四边形的最大面积。

输入

第一行包含整数 n (4 ≤ n ≤ 300)。接下来的 n 行中的每一行都包含两个整数: xi, yi (- 1000 ≤ xi, yi ≤ 1000) — 第 i 个特殊点的笛卡尔坐标。保证三点都不在同一条线上。保证没有两点重合。

输出

输出一个实数——特殊四边形的最大面积。如果答案的绝对误差或相对误差不超过 10 - 9,则认为答案是正确的。

示例

输入 #1

5
0 0
0 4
4 0
4 4
2 3

输出 #1

16.000000

注意

在测试示例中,我们可以选择前 4 个点作为四边形的顶点。它们形成一个边长为 4 的正方形,因此面积为 4·4 = 16。