#P3616. War

    ID: 1773 传统题 2000ms 256MiB 尝试: 296 已通过: 71 难度: 8 上传者: 标签>难度分类提高+/省选-概率与期望期望线性性指示变量数据结构K-D Tree按维度中位数划分包围盒剪枝位运算位集求并位计数计算几何平方距离比较数论快速幂CF25002014年国家集训队十五人互测鸣谢佚名上传

War

War

题目描述

小 x 所在的世界正在经历一场由 kk 个阵营参与的战争。每个阵营有若干炮塔,每座炮塔有攻击系统和防御系统。

第 ii 座炮塔能够攻击与它的欧氏距离不超过 rir_i 或曼哈顿距离不超过 aia_i 的炮塔。它只会攻击其他阵营的炮塔。被攻击的炮塔防御系统会崩溃。

每一轮独立地从所有炮塔中等概率选出一座,由它同时攻击所有可攻击的目标。防御系统已经崩溃的炮塔仍可被选中攻击,也仍可成为攻击目标。

如果一个阵营中所有炮塔的防御系统都完好,这个阵营就是完好的。没有炮塔的阵营始终完好。求进行 mm 轮后完好的阵营数量的期望。

输入格式

第一行三个整数 n,m,kn,m,k,分别表示炮塔数、攻击轮数和阵营总数。

接下来 nn 行每行五个整数 xi,yi,ri,ai,pix_i,y_i,r_i,a_i,p_i,分别表示第 ii 座炮塔的横坐标、纵坐标、欧氏攻击半径、曼哈顿攻击半径和阵营编号。

输出格式

输出一行一个实数,表示期望值。答案须与参考值的绝对误差不超过 10−310^{-3}。

样例

2 2 3
0 0 2 2 1
1 1 2 2 2
1.500

数据范围

0≤n,m,k≤350000\le n,m,k\le35000,1≤pi≤k1\le p_i\le k。炮塔的横纵坐标及两种攻击半径都是小于 1000010000 的非负整数。

数据生成时分开考虑每座炮塔的横坐标和纵坐标。