P1915 [NOI2010] Happy Growth

# Description Nemo is a carefree little fish with an initial weight of $w_0$. Cute Nemo wants to grow as fast as possible, so it needs to eat as much food as it can. Nemo’s favorite food is shrimp in the sea. Nemo knows the following about the food: there are $n$ shrimps in the sea, numbered from $1$ to $n$, where the weight of shrimp $i$ is $w_i$. Regard the ocean as an X-Y coordinate system. At time $0$, shrimp $i$ is at position $(x_i, y_i)$. Each shrimp moves in a straight line at a constant speed. The velocity vector of shrimp $i$ is $(p_i, q_i)$, which means that at time $t$, its position is $(x_i + p_i \cdot t, y_i + q_i \cdot t)$. Nemo is at position $(x_0, y_0)$ at time $0$. It can move freely in the sea, but its speed does not exceed $V$. Nemo hopes, through its own effort, to maximize the total weight of shrimps it eats within $T$ units of time (including time $T$). If Nemo and a shrimp reach the same position at the same time, and the shrimp’s weight is less than Nemo’s current weight, then Nemo can eat that shrimp. After Nemo eats a shrimp of weight $w_i$, its own weight increases by $w_i$. Note that shrimps do not eat Nemo, and shrimps do not attack each other. Nemo wants you to help make a growth plan so that the total weight of shrimps it eats is as large as possible.

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$ 时刻的位置和速度向量。

For the given $10$ input files `nemo1.in` $\sim$ `nemo10.in`, you need to submit the corresponding output files `nemo1.out` $\sim$ `nemo10.out`. The first line of the output file contains an integer $k$, indicating that in your growth plan, Nemo will eat $k$ shrimps. The second line contains a real number $w$, indicating the total weight of shrimps that Nemo eats in your plan. The next $k$ lines each contain $4$ numbers $t, x, y, s$. This means that at time $t$, Nemo eats shrimp numbered $s$ at position $(x, y)$. Here $t, x, y$ are real numbers, and $s$ is an integer. To ensure the precision of the checker, it is recommended to output all real numbers with at least $6$ digits after the decimal point. In the checker, two real numbers are considered equal if their absolute difference does not exceed $10^{-4}$.

### Sample explanation In this sample, Nemo eats shrimp $1$ at position $(2, 2)$ at time $5$. In fact, Nemo could reach $(2, 2)$ earlier, but the problem only requires that the speed not exceed $V$. ### Scoring For each dataset, we set $9$ scoring thresholds $a_{10}, a_9, \ldots, a_2$. If your output is invalid, you get zero points. Otherwise, let the increase in Nemo’s weight in your plan be $w_{user}$. Your score is determined by the following table: | Score | Condition | Score | Condition | | :---: | :-------------------: | :---: | :------------------: | | 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$ | ### How to use the checker In the checker directory, run `./checker in out` in the terminal. Here, in is the input file provided by the problem, and out is your answer file for that input. The checker only verifies the validity of your output. Final results are subject to the online judge. Thanks to @FlierKing for providing the SPJ and to @虞皓翔 for helping improve the SPJ. Translated by ChatGPT 5