[PKUSC2018]PKUSC

题目描述

九条可怜是一个爱玩游戏的女孩子。 最近她在玩一个无双割草类的游戏,平面上有 $n$ 个敌人,每一个敌人的坐标为 $x_i,y_i$。可怜有一个技能是在平面上画一个 $m$ 个点的简单多边形,并消灭所有**严格**在多边形内部的敌人。 不难发现如果想要快速的消灭敌人的话,只要画一个足够大的简单多边形就行了。但是这样的游戏性就太差了。于是可怜打算为游戏增加一定的随机性。 可怜在平面上随便画了一个 $m$ 个点的简单多边形 $(a_i,b_i)$。接下来可怜打算按照 $[-\pi,\pi)$ 上的均匀分布随机选取数字 $\alpha$(可以理解为等概率选取),并把这个简单多边形绕原点逆时针旋转 $\alpha$ 的角度(弧度制)。 现在可怜给你了每一个点的坐标,多边形的坐标,你的任务是帮助可怜计算在随机旋转后她期望可以消灭多少个敌人。

输入输出格式

输入格式


第一行四个整数 $n,m$。 接下来 $n$ 行每行两个整数 $x_i,y_i$ 描述了一个敌人的坐标。 接下来 $m$ 行每行两个整数 $a_i,b_i$ 按照逆时针的顺序描述了简单多边形的每一个顶点。

输出格式


输出一行一个整数表示期望值,保留五位小数。同时保证所有数据的小数点后第 $6$ 位在舍入前不会是 $4$ 和 $5$。

输入输出样例

输入样例 #1

4 4
0 0
1 0
-1 -1
0 1
0 0
1 0
1 1
0 1

输出样例 #1

0.50000

说明

### 样例解释 如果你对概率与期望不怎么了解,这儿给出一些 Hint: 1. 设 $P_i$ 为旋转之后恰好能消灭 $i$ 个敌人的概率,那么期望就是 $\sum_{i=1}^n iP_i$. 2. 计算 $P_i$ 的一个方法是,在所有 $[-\pi,\pi)$ 范围内的旋转角度中,旋转后恰好消灭 $i$ 个敌人的角度构成了 $t_i$ 个区间 $(l_j,r_j)$(开闭不影响),那么 $P_i=\frac{\sum_{j=1}^{t_i}(r_j-l_j)}{2\pi}$. 在这题中:能消灭 $0$ 个敌人的区间是 $[\frac{\pi}{2},\pi),[-\pi,-\frac{\pi}{2}]$,能消灭 $1$ 个敌人的区间是 $(-\frac{\pi}{2},0),(0,\frac{\pi}{2})$。于是 $P_0 = P_1=\frac{1}{2}$。所以答案为 $\frac{1}{2}=0.50000$. ### 数据范围 对于 $30\%$ 的数据,$n,m \leq 15$。 对于另外 $30\%$ 的数据,选择的简单多边形是一个凸多边形。 对于 $100\%$ 的数据,$n \leq 200, m \leq 500, |x|,|y| \leq 10^6$.