ACdream 1092-EOF女神の地鼠遊び

EOF女神の地鼠遊び
Time Limit: 2000/1000MS (Java/Others) 
Memory Limit: 128000/64000KB (Java/Others)
Submit  Statistic  Next Problem
Problem Description
      ACdreamのグループオーナーEOF女神(EndofFile)はネズミ遊びが大好きで、女神としては普通の人のように普通のゲームをすることはできないに違いない.EOF女神は直角座標系の原点に立ち、移動しません.ゲーム開始後、ある時点t[i]座標(x[i],y[i])に1匹のネズミが現れ、ネズミは非常に敏捷で、この時点でしか現れず、すぐに消えてしまい、EOFは女神として、もちろんハンマーでネズミを打つことを潔しとせず、彼女は念力からなるハンマーでネズミを打つ(Orz...)、功力が限られているため、女神は念力ハンマーしかなく、念力ハンマーの移動速度は毎秒v単位の長さであり、あるネズミに対しては、ネズミが現れた瞬間にハンマーがこの座標に当たったとしても、ネズミはp[i]の確率で当たってしまい、回避に成功するとすぐに消える.EOF女神にはもう一つの超能力がある:未来を予知する!女神は最初からすべてのネズミの出現座標、出現時刻、さらにはヒット確率(Orrrrrrrrrrrrz)を知っていた.女神は彼女のゲームの過程の中でネズミの数に当たった数学の期待がどれだけあるかを知りたいと思っています.
(Note:女神は0 sの瞬間に任意のネズミを撃つことができる)
Input
      第1の動作は、テストデータのグループ数を表す正の整数Tである.
      各試験データのセットについて、まず2つの正の整数n、v(n<1000、v<1000)はラットの個数を表す.
      次にn行で、各行には3つの整数x[i],y[i],t[i],(-1000および浮動小数点数p[i](0<=p[i]<=1)があり、それぞれi匹目のネズミの出現座標、時刻およびヒット確率を表す.
Output
      各グループのデータについて、最適な戦略の下で女神がネズミの個数に当たった数学的期待を出力します.小数点以下の6桁の数字を保持します.
Sample Input

2
2 1
1 0 0 0.8
0 1 1 0.4
4 2
1 0 0 0.5
1 1 1 0.6
0 1 2 0.7
0 0 3 0.8

Sample Output

0.800000
2.600000

Hint
第1群のサンプルは、2つのマウスがルート番号2から離れているため、出現時間が1つしか異なるため、1匹のマウスしか選択できないため、最適な戦略は1匹のマウスを打つことであり、数学的には0.8が望ましい.
第2の群のサンプルは、4つのネズミを順次打ち終えることができるので、数学は確率の和2.6と期待される.
Source
mathlover
Manager
mathlover

#include 
#include 
#include 
#include 
#include 

using namespace std;

struct node
{
    int x,y,t;
    double p;
} a[1009];
double dp[1009];

int cmp(node xx,node yy)
{
    return xx.t=0)
                    dp[i]=max(dp[i],dp[j]+a[i].p);
            ans=max(dp[i],ans);
        }
        printf("%.6lf
",ans);
    }
    return 0;
}