EOF女神的打地鼠游戏

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      ACdream的群主EOF女神(EndofFile)很喜欢玩打地鼠游戏,作为女神,肯定不能像正常人去玩这个看似普通的游戏。EOF女神站在直角坐标系的原点上,不移动。游戏开始后,某一时刻t[i]在坐标(x[i],y[i])处会出现一只地鼠,地鼠十分敏捷,只在这一个时刻出现,马上就消失,EOF作为女神,当然不屑于用锤子去打地鼠,她用念力组成的锤子去打地鼠(Orz…),由于功力有限,女神只有一个念力锤子,念力锤子的移动速度为每秒v个单位长度,并且对于某一只地鼠,即使地鼠出现的瞬间锤子打到了该坐标,地鼠仍然有p[i]概率会击中,一旦闪避成功,便会马上消失。EOF女神还有一项超能力:预知未来!女神一开始便知道所有地鼠的出现坐标,出现的时刻,甚至是击中的概率(Orrrrrrrrrrz)。女神想知道她整个游戏过程中打中地鼠个数的数学期望是多少?

(Note: 女神可以在0s的瞬间击打任意一个地鼠)

Input

      第一行为一个正整数T,代表测试数据的组数;

      对于每一组测试数据,首先是两个正整数n,v(n<1000,v<1000)代表地鼠的个数。

      接下来是n行,每一行有三个整数x[i],y[i],t[i],(-1000<x[i],y[i]<1000,0<=t[i]<=10^9)以及一个浮点数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

第一组样例,由于两个地鼠相距根号2,出现的时间只相差1,因此只能挑一只打,因此最优策略为打第一只地鼠,数学期望为0.8

第二组样例,可以依次把四个地鼠打完,因此数学期望为概率之和2.6

Source

mathlover

Manager

Information
Solved Number151
Submit Number375
Problem Tags
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel