Description

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

Input

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

Output

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

Sample Input

2 2 3

0 0 2 2 1

1 1 2 2 2

Sample Output

1.500

 

 

建完k-d树直接查找记得打标记就好了。

然而某邻接表写炸，RE了两发，最后#8还是不错的

从网上拷来3份标程（CA，Claris，鸟神），加上自己的AC代码共4份，随机造数据居然能出现4个不同的答案……（CA爷的代码最不和群

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ii inline int#define MN 36000#define MM 5000000using namespace std;int n,m,f,ro=0,num=0,xx,X,o,la=0,NO,l[MN+1],k;double MMH=0;char cs;ii read(){    cs=getchar();xx=0;f=1;    while(cs<'0'||cs>'9') {
     if (cs=='-') f=-1;cs=getchar();}    while(cs>='0'&&cs<='9') xx=xx*10+cs-48,cs=getchar();    return xx*f;}struct tr{    int x,y,r,a;    friend bool operator<(tr a,tr b){
     if (X) return a.y
            
              G[MN+1];vector 
             
               V[MN+1];ii S(int x){ return x*x;}ii A(int a,int b){ return a>b?a:b;}ii I(int a,int b){ return a
              
               >1; nth_element(a+l,a+mid,a+r+1); t[mid].xa=t[mid].xi=a[mid].x; t[mid].ya=t[mid].yi=a[mid].y; t[mid].l=t[mid].r=0; if (l