PEG Judge - NOI '10 - Happily Growing

National Olympiad in Informatics, China, 2010

Day 2, Problem 3 - Happily Growing

Nemo is a carefree little fish. His initial birth weight is w₀. Cute little Nemo wishes to grow up as fast as possible, and thus will need to eat as much food as possible. Nemo's favorite food is little shrimps from the ocean.

Nemo's understanding of the available food is as follows: There are a total of n shrimps in the ocean, numbered from 1 to n. Shrimp i will have a weight of w_i. The ocean can be represented as a Cartesian plane. At time 0, shrimp i will be at position (x_i, y_i). In the ocean, shrimps move in straight lines at constant velocities. Shrimp i's velocity vector is (p_i, q_i), which means at time i, its position will be (x_i + p_i*t, y_i + q_i*t).

At time 0, Nemo's position will be (x₀, y₀). He may move however he pleases in the ocean, but his speed cannot exceed V. Through his own hard work, Nemo wishes to eat the largest weight of shrimp as possible within T units of time (containing T moments). When Nemo and a little shrimp moves onto the same position at the same time, and the weight of the shrimp is smaller than Nemo's weight at that time, then Nemo will be able to successfully eat up the shrimp. When Nemo eats a shrimp of weight w_i, his own weight will increase by w_i. Note: shrimps cannot eat Nemo, nor will they cannibalize each other.

Nemo wishes for you to help him design a growth plan, so that the weight of the shrimp he eats is as large as possible.

Input Format

There are 10 test cases nemo1.in ~ nemo10.in that will be given to your program (through standard input). They can be downloaded here for you to study: nemo.zip

Line 1 of input contains an integer from 1 to 10, representing the test case number. Test case nemoi.in will have i on its first line.
Line 2 contains five real numbers w₀, V, T, x₀, and y₀. Respectively, the represent Nemo's initial weight, maximum speed, time to eat shrimp, and initial position at time 0.
Line 3 contains a single integer n, representing the number of shrimp there are in the ocean.
For the following n lines, each line contains 5 real numbers w_i, x_i, y_i, p_i, and q_i, representing the weight of shrimp i, its position at time 0, and its velocity vector.

Output Format

Line 1 of output should consists a single integer k, representing the number of shrimps Nemo will eat in your plan.
Line 2 should consists of a single real number w, representing the total weight of shrimps that Nemo will eat in your plan.
For the following k lines, each line should contain 4 numbers t, x, y, and s. This indicates that at time t, Nemo should be at position (x, y) to eat shrimp s. Here, t, x, and y are real numbers, while s is an integer.
To ensure that your answer is precise enough, we suggest outputting all real numbers to 6 digits after the decimal. During grading, two real numbers are considered equivalent if their error (i.e. absolute difference) does not exceed 10⁻⁴.

Sample Input

Sample Output

1
5
5 2 2 1

Explanation

In the sample solution at time 5, Nemo will be at position (2, 2) to eat shrimp number 1. Nemo can actually reach (2, 2) much earlier, since the problem only requires his speed to merely not exceed V.

Scoring

For each test case, we will have 9 grading parameters a₁₀, a₉, …, a₂. If your output is invalid, then you will be given a score of 0. Otherwise, assuming that Nemo's weight increase in your solution is w_user, then your score out of 10 for the test case will be determined as follows:

Score	Condition
10	`w`_user ≥ `a`₁₀
9	`w`_user ≥ `a`₉
8	`w`_user ≥ `a`₈
7	`w`_user ≥ `a`₇
6	`w`_user ≥ `a`₆
5	`w`_user ≥ `a`₅
4	`w`_user ≥ `a`₄
3	`w`_user ≥ `a`₃
2	`w`_user ≥ `a`₂
1	`w`_user > 0