#6437. 「PKUSC2018」PKUSC

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zjq

题目描述

九条可怜是一个爱玩游戏的女孩子。

最近她在玩一个无双割草类的游戏,平面上有 nn 个敌人,每一个敌人的坐标为 xi,yix_i,y_i。可怜有一个技能是在平面上画一个 mm 个点的简单多边形,并消灭所有严格在多边形内部的敌人。

不难发现如果想要快速的消灭敌人的话,只要画一个足够大的简单多边形就行了。但是这样的游戏性就太差了。于是可怜打算为游戏增加一定的随机性。

可怜在平面上随便画了一个 mm 个点的简单多边形 (ai,bi)(a_i,b_i)。接下来可怜打算按照 [π,π)[-\pi,\pi) 上的均匀分布随机选取数字 α\alpha(可以理解为等概率选取),并把这个简单多边形绕原点逆时针旋转 α\alpha 的角度(弧度制)。

现在可怜给你了每一个点的坐标,多边形的坐标,你的任务是帮助可怜计算在随机旋转后她期望可以消灭多少个敌人。

输入格式

第一行四个整数 n,mn,m

接下来 nn 行每行两个整数 xi,yix_i,y_i 描述了一个敌人的坐标。

接下来 mm 行每行两个整数 ai,bia_i,b_i 按照逆时针的顺序描述了简单多边形的每一个顶点。

输出格式

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

样例

样例输入

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

样例输出

0.50000

样例解释

如果你对概率与期望不怎么了解,这儿给出一些 Hint:

  1. PiP_i 为旋转之后恰好能消灭 ii 个敌人的概率,那么期望就是 i=1niPi\sum_{i=1}^n iP_i.
  2. 计算 PiP_i 的一个方法是,在所有 [π,π)[-\pi,\pi) 范围内的旋转角度中,旋转后恰好消灭 ii 个敌人的角度构成了 tit_i 个区间 (lj,rj)(l_j,r_j)(开闭不影响),那么 Pi=j=1ti(rjlj)2πP_i=\frac{\sum_{j=1}^{t_i}(r_j-l_j)}{2\pi}.

在这题中:能消灭 00 个敌人的区间是 [π2,π),[π,π2][\frac{\pi}{2},\pi),[-\pi,-\frac{\pi}{2}],能消灭 11 个敌人的区间是 (π2,0),(0,π2)(-\frac{\pi}{2},0),(0,\frac{\pi}{2})。于是 P0=P1=12P_0 = P_1=\frac{1}{2}。所以答案为 12=0.50000\frac{1}{2}=0.50000.

数据范围与提示

对于 30%30\% 的数据,n,m15n,m \leq 15

对于另外 30%30\% 的数据,选择的简单多边形是一个凸多边形。

对于 100%100\% 的数据,n200,m500,x,y106n \leq 200, m \leq 500, |x|,|y| \leq 10^6.