← 返回题目列表

Codeforces · 559/D

D. 随机发生器

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

杰拉德厌倦了用通常的六面骰子玩棋盘游戏,他买了一个名为随机发生器的玩具。其功能如下。

随机发生器有自己的坐标平面,在该坐标平面上绘制严格凸多边形,该多边形称为基本多边形。如果摇动随机发生器,它会绘制一些非退化(即具有非零面积)凸多边形,其顶点位于基本多边形的某些顶点处。滚动的结果(更准确地说,摇动的结果)被认为是具有整数坐标的点的数量,这些点严格位于所选多边形内部(不考虑边界上的点)。现在杰拉德想知道:摇动随机发生器的预期结果是什么?

在摇动过程中,随机发生器会考虑所有可能的非退化凸多边形,其顶点位于基本多边形的顶点。我们假设有 k 个版本的多边形。然后随机发生器以 $$\frac{1}{k}$$ 的概率选择它们中的每一个。

输入

输入的第一行包含一个整数 n (3 ≤ n ≤ 100 000) — 基本多边形的顶点数。

接下来的 n 行包含基本多边形顶点的坐标。这些行的第 i 行包含两个整数 xi 和 yi (- 109 ≤ xi, yi ≤ 109) — 多边形第 i 个顶点的坐标。顶点按逆时针顺序给出。

输出

打印所寻求的期望值,绝对或相对误差最多为 10 - 9。

示例

输入 #1

4
0 0
2 0
2 2
0 2

输出 #1

0.2

输入 #2

5
0 0
2 0
2 2
1 3
0 2

输出 #2

0.8125

注意

如果多边形是凸多边形并且其顶点不位于同一直线上,则该多边形称为严格凸多边形。

假设随机变量的值为 x1, ..., xn ,相应的概率为 p1, ..., pn。那么这个变量的期望值就等于$$\sum_{i=1}^{n} x_{i} p_{i}$$。