← 返回题目列表

Codeforces · 30/C

C. 射击场

中文机器翻译题面 查看原题

一个温暖晴朗的日子,国王科帕决定参观位于中央公园的射击场,并尝试赢得大奖——粉色大毛绒熊猫。国王不擅长射击,所以他邀请你来帮助他。

射击场是一个无限大的垂直平面,其上有笛卡尔坐标系。目标是该平面上的点。每个目标由它的坐标 xi 和 yi、出现时间 ti 和数字 pi 来描述,这给出了 Copa 在瞄准该目标时击中该目标的概率。

目标瞬间出现并立即消失,因此 Copa 只有在此时瞄准 (xi, yi) 时才能击中目标。飞机上瞄准镜的移动速度等于1。Copa事先知道目标的所有信息(记住,他是国王!)。他希望以最佳方式进行比赛,从而最大化命中目标数量的预期值。他此刻可以瞄准任何目标0。

输入

第一行包含整数 n (1 ≤ n ≤ 1000) — 射击场中的目标数量。接下来是 n 行,每行描述一个目标。每个描述由四个数字 xi、yi、ti、pi 组成(其中 xi、yi、ti — 整数,- 1000 ≤ xi、yi ≤ 1000、0 ≤ ti ≤ 109,实数 pi 给出小数点后不超过 6 位数字,0 ≤ pi ≤ 1)。任何两个目标都不能位于同一点。

输出

输出国王射中目标数量的最大期望值。如果您的答案与正确答案的差异不超过 10 - 6,则您的答案将被接受。

示例

输入 #1

1
0 0 0 0.5

输出 #1

0.5000000000

输入 #2

2
0 0 0 0.6
5 0 5 0.7

输出 #2

1.3000000000