CF54E Vacuum Сleaner

在一个冬夜，刺猬正舒适地坐在家中的扶手椅上换着电视频道。偶然切换到《TopShop》节目时，刺猬正准备换台，突然被一个新奇发明的广告吸引住了。 实际上，广告宣传的是一款吸尘器，名为“Marvellous Vacuum”，更神奇的是，它在打扫时甚至不需要人类操作！吸尘器能自己在房间里移动：它会朝某个方向前进，遇到障碍物时会自动选择新的方向。迟早，这个吸尘器会遍历整个房间，把所有地方都打扫干净。刺猬想到自己每次打扫最少都要花上半天时间，不禁非常想买这个神器。 然而，刺猬很快发现这个吸尘器至少有一个弱点：在房间的角落里，它打扫不彻底，因为受自身形状影响，经常无法到达角落。为了实际估算这个缺点有多严重，刺猬让你为他写一个相应的程序。 你将得到吸尘器从顶部视角的形状。我们只考虑吸尘器形状为凸多边形的情况。房间视作一个无限大的长方形。现在只考虑房间的一个角落，要求找到吸尘器的一种旋转，使其被推入角落后，在角落里留下的未覆盖面积最小。

第一行包含一个整数 $N$，表示吸尘器形状多边形的顶点数（$3 \leq N \leq 4 \cdot 10^{4}$）。接下来 $N$ 行，每行包含两个整数，表示多边形一个顶点的坐标。所有坐标均为整数，且其绝对值不超过 $10^6$。 保证所给多边形非退化且为凸多边形（没有三点共线）。多边形的顶点顺序为顺时针或逆时针给出。

输出一个实数，表示最小可能的未覆盖面积。答案的绝对误差或相对误差不超过 $10^{-6}$ 均视为正确。

由 ChatGPT 5 翻译