#P3616. War
War
War
题目描述
小 x 所在的世界正在经历一场由 个阵营参与的战争。每个阵营有若干炮塔,每座炮塔有攻击系统和防御系统。
第 座炮塔能够攻击与它的欧氏距离不超过 或曼哈顿距离不超过 的炮塔。它只会攻击其他阵营的炮塔。被攻击的炮塔防御系统会崩溃。
每一轮独立地从所有炮塔中等概率选出一座,由它同时攻击所有可攻击的目标。防御系统已经崩溃的炮塔仍可被选中攻击,也仍可成为攻击目标。
如果一个阵营中所有炮塔的防御系统都完好,这个阵营就是完好的。没有炮塔的阵营始终完好。求进行 轮后完好的阵营数量的期望。
输入格式
第一行三个整数 ,分别表示炮塔数、攻击轮数和阵营总数。
接下来 行每行五个整数 ,分别表示第 座炮塔的横坐标、纵坐标、欧氏攻击半径、曼哈顿攻击半径和阵营编号。
输出格式
输出一行一个实数,表示期望值。答案须与参考值的绝对误差不超过 。
样例
2 2 3
0 0 2 2 1
1 1 2 2 2
1.500
数据范围
,。炮塔的横纵坐标及两种攻击半径都是小于 的非负整数。
数据生成时分开考虑每座炮塔的横坐标和纵坐标。