A86015.「PKUSC2018」PKUSC
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:512MB
题目描述
九条可怜是一个爱玩游戏的女孩子。
最近她在玩一个无双割草类的游戏,平面上有 n 个敌人,每一个敌人的坐标为 xi,yi。可怜有一个技能是在平面上画一个 m 个点的简单多边形,并消灭所有严格在多边形内部的敌人。
不难发现如果想要快速的消灭敌人的话,只要画一个足够大的简单多边形就行了。但是这样的游戏性就太差了。于是可怜打算为游戏增加一定的随机性。
可怜在平面上随便画了一个 m 个点的简单多边形 (ai,bi)。接下来可怜打算按照 [−π,π) 上的均匀分布随机选取数字 α(可以理解为等概率选取),并把这个简单多边形绕原点逆时针旋转 α 的角度(弧度制)。
现在可怜给你了每一个点的坐标,多边形的坐标,你的任务是帮助可怜计算在随机旋转后她期望可以消灭多少个敌人。
输入格式
第一行四个整数 n,m。
接下来 n 行每行两个整数 xi,yi 描述了一个敌人的坐标。
接下来 m 行每行两个整数 ai,bi 按照逆时针的顺序描述了简单多边形的每一个顶点。
输出格式
输出一行一个整数表示期望值,保留五位小数。同时保证所有数据的小数点后第 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≤15。
对于另外 30% 的数据,选择的简单多边形是一个凸多边形。
对于 100% 的数据,n≤200,m≤500,∣x∣,∣y∣≤106.