← 返回题目列表

Codeforces · 1578/F

F. 取景照片

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

金星上发现生命!更重要的是,生命形式看起来是凸多边形的。一个国际财团正在设计一个探测器,用于发送到金星拍照,但他们需要估计发回照片所需的带宽。

当探测器拍摄生命形式的照片并希望将其发送回地球时,所需的带宽与边界框(换句话说,包含生命形式的最小轴对齐矩形)的面积成正比。生命体的形状和大小是已知的,但相对于相机的方向是随机的。因此,您必须确定所有方向上边界框的预期(平均)面积。

输入

输入将生命形式的形状描述为二维凸多边形。

输入的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 200\,000$$$) — 顶点数。其余 $$$n$$$ 行每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$-10^9 \le x, y \le 10^9$$$) - 顶点的坐标。顶点按逆时针顺序给出,并且没有三个顶点位于一条直线上。

输出

输出包含多边形边界框的预期面积的单行。您的答案的绝对或相对误差最多为 $$$10^{-6}$$$。

示例

输入 #1

4
0 0
10 0
10 10
0 10

输出 #1

163.661977237

输入 #2

5
0 0
10 0
15 8
5 20
-5 7

输出 #2

365.666028588

注意

这些图片显示了示例生命形式和各种相机方向。