← 返回题目列表

Codeforces · 54/E

E. 真空吸尘器

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

一个冬天的夜晚,刺猬在家里舒适的扶手椅上放松,点击着电视频道。刺猬无意中看到了一期《TopShop》,正准备换台,突然被一则新奇妙发明的广告拦住了。

实际上,那里刊登了真空吸尘器的广告。它被称为“Marvelous Vacuum”,它在清洁时甚至不需要人类来操作!真空吸尘器可以自行在公寓周围移动:它会向某个方向移动,如果它碰到那里的障碍物,它会自动选择一个新方向。迟早这个吸尘器会穿过整个房间并把它全部清理干净。想起刺猬每次打扫卫生要花多少时间(肯定不少于半天),他就迫不及待地想买下这个奇迹。

然而,刺猬很快就明白了这款吸尘器至少有一个弱点:它不能很好地清洁房间的角落,因为它的形状常常无法到达角落。为了估计这个缺点在实践中有多严重,刺猬要求你为他编写相应的程序。

您将在俯视图中看到吸尘器的形状。我们将仅考虑真空吸尘器被表示为凸多边形的情况。房间是一个无限大的矩形。我们考虑这个房间的一个角落,并希望找到一种真空吸尘器的旋转方式,以便将其推入该角落时,将在角落中留下尽可能小的区域未被覆盖。

输入

第一行包含一个整数 N,表示真空吸尘器多边形的顶点数 (3 ≤ N ≤ 4·104)。然后沿着 N 行,每行包含两个数字——多边形顶点的坐标。所有坐标均为整数且绝对值不超过106。

保证给定的多边形是非退化且凸的(没有三个点位于同一条线上)。多边形顶点以顺时针或逆时针方向给出。

输出

打印可能的最小未覆盖区域。如果答案与正确答案的绝对或相对误差在 10 - 6 以内,则答案将被接受。

示例

输入 #1

4
0 0
1 0
1 1
0 1

输出 #1

0.00000000000000000000

输入 #2

8
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
-2 1
-1 2

输出 #2

0.50000000000000000000