BZPRO

#3616. War

内存限制：256 MiB 时间限制：20 Sec
提交 提交记录 讨论

题目描述

小x所在的世界正在经历一场在k个阵营之间的战争。每个阵营有若干个炮塔，每个炮塔由攻击系统和防御系统组成。第i个炮塔可以攻击到离它欧几里德距离小于等于ri 或者曼哈顿距离小于等于ai的炮塔，被攻击到的炮塔防御系统就会崩溃，同一联盟的炮塔不会被攻击到。每次会随机选择一个炮塔攻击它能打到的所有炮塔，问进行m轮后期望剩下多少个阵营，使得这些阵营拥有的炮塔的防御系统全部完好。防御系统崩溃的炮塔还是会被打到的。值得注意的是，如果一个联盟没有任何炮塔，那么不管怎样它都是完好的。

输入格式

　　输入文件第一行有三个整数n、m、k，分别表示炮塔数目、攻击轮数以及联盟个数。 接下去n行每行有五个正整数xi、yi、ri、ai、pi，其中xi、yi表示炮塔坐标，p表示炮塔所属于阵营。

输出格式

　　输出一行一个实数表示答案，你的输出与标准输出的误差在1e-3以内会被认为是正确的。

样例

样例输入


			
2 2 3

0 0 2 2 1

1 1 2 2 2

样例输出


			
1.500

数据范围与提示

　　100%的数据， 0 <= n、m、k <= 35000，1 <= pi <= k，其余所有数字均非负且小于10000，保证在数据生成时不考虑一个点的具体位置，而将它的横纵坐标分开考虑。


BZPRO Powered by Remmina.
Github Repository