Background

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.

Output Format

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}$.

5 1 6 0 0
1
5 2 2 0 0

1
5
5 2 2 1

Hint

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:

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