[NOI2010]成长快乐

题目描述

Nemo 是一条无忧无虑的小鱼,它的初始体重为 $w_0$。可爱的 Nemo 希望自己能够尽快地成长,因此需要吃尽量多的食物。Nemo 最喜爱的食物是海里的小虾。 已知 Nemo 对食物的情况了解如下:大海里共有 $n$ 只小虾,从 $1$ 到 $n$ 编号,其中编号为 $i$ 的小虾的重量为 $w_i$。将大海看作一个 X-Y 坐标系,在 $0$ 时刻编号为 $i$ 的小虾所在的位置为 $(x_i, y_i)$。小虾在大海中作匀速直线运动,其中编号为 $i$ 的小虾的速度向量为 $(p_i, q_i)$,即在时刻 $t$,它的位置为 $(x_i+p_i \cdot t,y_i+q_i \cdot t)$。 Nemo 在 $0$ 时刻的位置为 $(x_0, y_0)$,它可以在海中随意移动,但速度不超过 $V$。Nemo 希望通过自己的努力,在 $T$ 个单位时间内(含 $T$ 时刻)吃到的小虾重量总和尽量大。 当 Nemo 与某只小虾同时移动到同一个位置上,且小虾的重量小于 Nemo 当时的重量,则 Nemo 可以将该小虾吃掉。当 Nemo 吃掉重量为 $w_i$ 的小虾之后,它的体重将增加 $w_i$。注意,小虾不会吃 Nemo,且小虾之间也不会自相残杀。 Nemo 希望你来帮助它制定一个成长计划,使得它吃掉的小虾重量总和尽量大。

输入输出格式

输入格式


该题为提交答案型试题,所有输入数据 `nemo1.in` $\sim$ `nemo10.in` 已在试题目录下。 **[数据以及checker下载](http://pan.baidu.com/s/1dEDLQud)** 对于每个数据,输入文件中第一行为五个实数 $w_0, V, T, x_0, y_0$。分别表示 Nemo 的初始体重、最大移动速度、时间限制以及 Nemo 在 $0$ 时刻的位置。 第二行为一个整数 $n$,表示大海中小虾的只数。 接下来 $n$ 行,每行 $5$ 个实数,包括 $w_i, x_i, y_i, p_i, q_i$,分别表示编号为 $i$ 的小虾的重量、在 $0$ 时刻的位置和速度向量。

输出格式


针对给定的 $10$ 个输入文件 `nemo1.in` $\sim$ `nemo10.in`,你需要分别提交你的输出文件 `nemo1.in` $\sim$ `nemo10.in`。 输出文件第一行包含一个整数 $k$。表示在你的成长计划中,Nemo 将吃到 $k$ 只小虾。 第二行包含一个实数 $w$,表示在你的成长计划中,Nemo 吃到的小虾的重量总和。 接下来 $k$ 行,每行 $4$ 个数 $t, x, y, s$。表示在时刻 $t$,Nemo 在位置 $(x, y)$ 处吃掉了编号为 $s$ 的小虾。其中 $t, x, y$ 为实数,$s$ 为整数。 为保证验证程序的精度,所有实数建议至少输出到小数点后 $6$ 位。在验证程序中,两个实数绝对误差不超过 $10^{-4}$ 时,即视为相等。

输入输出样例

输入样例 #1

5 1 6 0 0
1
5 2 2 0 0

输出样例 #1

1
5
5 2 2 1

说明

### 样例解释 在这个样例中,Nemo 在时刻 $5$ 在位置 $(2, 2)$ 吃掉了 $1$ 号小虾。其实 Nemo 到达 $(2, 2)$ 的时间可以更早,但题中仅要求速度不超过 $V$ 即可。 ### 评分方法 对于每组数据,我们设置了 $9$ 个评分参数 $a_{10},a_9, \ldots ,a_2$。如果选手的输出不合法,则得零分。否则,设在你的方案中,Nemo 体重的增加量为 $w_{user}$,你的分数将会由下表给出: | 得分 | 条件 | 得分 | 条件 | | :--: | :--------------------: | :--: | :-----------------: | | 10 | $w_{user} \geq a_{10}$ | 5 | $w_{user} \geq a_5$ | | 9 | $w_{user} \geq a_9$ | 4 | $w_{user} \geq a_4$ | | 8 | $w_{user} \geq a_8$ | 3 | $w_{user} \geq a_3$ | | 7 | $w_{user} \geq a_7$ | 2 | $w_{user} \geq a_2$ | | 6 | $w_{user} \geq a_6$ | 1 | $w_{user} \gt 0$ | ### checker 使用方法 在 checker 目录下,在终端输入 `./checker in out`。 其中 in 为题目提供的输入文件,out 为你对于该输入文件给出的答案文件。 校验器将只检查你的答案的合法性,结果以在线评测为准。 感谢 @FlierKing 提供 spj 以及 @虞皓翔 帮助完善 spj。