杰拉德厌倦了用通常的六面骰子玩棋盘游戏,他买了一个名为随机发生器的玩具。其功能如下。
随机发生器有自己的坐标平面,在该坐标平面上绘制严格凸多边形,该多边形称为基本多边形。如果摇动随机发生器,它会绘制一些非退化(即具有非零面积)凸多边形,其顶点位于基本多边形的某些顶点处。滚动的结果(更准确地说,摇动的结果)被认为是具有整数坐标的点的数量,这些点严格位于所选多边形内部(不考虑边界上的点)。现在杰拉德想知道:摇动随机发生器的预期结果是什么?
在摇动过程中,随机发生器会考虑所有可能的非退化凸多边形,其顶点位于基本多边形的顶点。我们假设有 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}$$。