A5990. 「PKUSC2018」PKUSC
编程题
省选/NOI-
知识点
题目描述
九条可怜是一个爱玩游戏的女孩子。
最近她在玩一个无双割草类的游戏，平面上有 $n$ 个敌人，每一个敌人的坐标为 $x_i,y_i$。可怜有一个技能是在平面上画一个 $m$ 个点的简单多边形，并消灭所有**严格**在多边形内部的敌人。
不难发现如果想要快速的消灭敌人的话，只要画一个足够大的简单多边形就行了。但是这样的游戏性就太差了。于是可怜打算为游戏增加一定的随机性。
可怜在平面上随便画了一个 $m$ 个点的简单多边形 $(a_i,b_i)$。接下来可怜打算按照 $[-\pi,\pi)$ 上的均匀分布随机选取数字 $\alpha$（可以理解为等概率选取），并把这个简单多边形绕原点逆时针旋转 $\alpha$ 的角度（弧度制）。
现在可怜给你了每一个点的坐标，多边形的坐标，你的任务是帮助可怜计算在随机旋转后她期望可以消灭多少个敌人。
最近她在玩一个无双割草类的游戏，平面上有 $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$ 按照逆时针的顺序描述了简单多边形的每一个顶点。
接下来 $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
说明/提示
对于 $30\%$ 的数据，$n,m \leq 15$。
对于另外 $30\%$ 的数据，选择的简单多边形是一个凸多边形。
对于 $100\%$ 的数据，$n \leq 200, m \leq 500, |x|,|y| \leq 10^6$.
对于另外 $30\%$ 的数据，选择的简单多边形是一个凸多边形。
对于 $100\%$ 的数据，$n \leq 200, m \leq 500, |x|,|y| \leq 10^6$.