CF30C Shooting Gallery

在一个温暖而阳光明媚的日子里，国王 Copa 决定前往中央公园的射击场，尝试赢得大奖——一只巨大的粉色毛绒熊猫。由于国王并不擅长射击，于是邀请了你来帮助他。 射击场被视为一个无限大的竖直平面，该平面上建立了直角坐标系。每一个靶子由其坐标 $x_{i}$ 和 $y_{i}$、出现时间 $t_{i}$ 以及数字 $p_{i}$ 描述，$p_{i}$ 表示 Copa 在瞄准该靶子时击中的概率。 每个靶子在某一时刻出现并瞬间消失，因此 Copa 只能在 $t_{i}$ 时枪口正好瞄准 $(x_{i},y_{i})$ 时才有机会击中该靶。枪口在平面上移动的速度为 $1$。Copa 事先知道所有靶子的全部信息（毕竟他是国王！）。他希望以最优策略玩耍，使得击中靶子的期望数量最大化。在 $0$ 时刻他可以瞄准任意一个靶子。

第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示靶子的数量。接下来有 $n$ 行，每行描述一个靶子，包含四个数 $x_{i}$、$y_{i}$、$t_{i}$、$p_{i}$（其中 $x_{i}$、$y_{i}$、$t_{i}$ 均为整数，$-1000 \leq x_{i}, y_{i} \leq 1000$，$0 \leq t_{i} \leq 10^{9}$，实数 $p_{i}$ 最多有 6 位小数，$0 \leq p_{i} \leq 1$）。任意两个靶子的坐标都不相同。

输出国王最大能够击中的靶子的期望数量。只要你的答案与标准答案的误差不超过 $10^{-6}$，即可被接受。

由 ChatGPT 5 翻译