P2831 [NOIP 2016 Senior] Angry Birds

NOIP 2016 Senior Day 2 Task 3.

Kiana has recently become addicted to a magical game. Simply put, this game takes place on a plane. There is a slingshot at $ (0, 0) $. Each time, Kiana can use it to launch a red bird toward the first quadrant. The flight trajectory of a bird is a curve of the form $ y = a x^2 + b x $, where $ a, b $ are parameters chosen by Kiana and must satisfy $ a < 0 $, with $ a, b $ being real numbers. When a bird falls back to the ground (i.e., the $ x $-axis), it disappears instantly. In a certain level of the game, there are $ n $ green pigs in the first quadrant of the plane. The $ i $-th pig is at coordinates $ \left( x_i, y_i \right) $. If a bird’s trajectory passes through $ \left( x_i, y_i \right) $, then the $ i $-th pig will be eliminated, and the bird will continue along its original trajectory. If a bird’s trajectory does not pass through $ \left( x_i, y_i \right) $, then that bird’s entire flight has no effect on the $ i $-th pig. For example, if two pigs are at $ (1, 3) $ and $ (3, 3) $, Kiana can choose to launch a bird with trajectory $ y = -x^2 + 4x $, and both pigs will be eliminated by this bird. The goal of the game is to eliminate all the pigs by launching birds. Each level of this magical game is difficult for Kiana, so she also entered some mysterious commands to make it easier to complete the game. These commands are detailed in Input Format. Assume the game has $ T $ levels. Now Kiana wants to know, for each level, the minimum number of birds needed to eliminate all the pigs. Since she cannot compute it herself, she hopes you will tell her.

The first line contains a positive integer $ T $, the total number of levels in the game. Then, for each of the $ T $ levels, the first line contains two non-negative integers $ n, m $, representing the number of pigs in that level and the type of mysterious command Kiana entered, respectively. The next $ n $ lines each contain two positive real numbers $ x_i, y_i $, indicating that the $ i $-th pig is at $ (x_i, y_i) $. It is guaranteed that no two pigs in the same level share identical coordinates. If $ m = 0 $, it means Kiana entered a command that has no effect. If $ m = 1 $, then this level satisfies: at most $ \lceil n / 3 + 1 \rceil $ birds are sufficient to eliminate all pigs. If $ m = 2 $, then this level satisfies: there is an optimal solution in which one bird eliminates at least $ \lfloor n / 3 \rfloor $ pigs. It is guaranteed that $ 1 \leq n \leq 18 $, $ 0 \leq m \leq 2 $, and $ 0 < x_i, y_i < 10 $. All real numbers in the input are given to two decimal places. In the above, the symbols $ \lceil c \rceil $ and $ \lfloor c \rfloor $ denote the ceiling and floor of $ c $, respectively. For example: $ \lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3 $.

For each level, output one line with a positive integer: the minimum number of birds needed to eliminate all pigs in that level.

Sample Explanation 1. There are two levels in this set of testdata. In the first level, as in the Description, $ 2 $ pigs are at $ (1.00, 3.00) $ and $ (3.00, 3.00) $. Launching one bird with trajectory $ y = -x^2 + 4x $ is enough to eliminate them. In the second level, there are $ 5 $ pigs, and by observation they all lie on the parabola $ y = -x^2 + 6x $, so Kiana needs to launch only one bird to eliminate all pigs. Constraints | Test point ID | $n\leqslant$ | $m=$ | $T\leqslant$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $2$ | $0$ | $10$ | | $2$ | $2$ | $0$ | $30$ | | $3$ | $3$ | $0$ | $10$ | | $4$ | $3$ | $0$ | $30$ | | $5$ | $4$ | $0$ | $10$ | | $6$ | $4$ | $0$ | $30$ | | $7$ | $5$ | $0$ | $10$ | | $8$ | $6$ | $0$ | $10$ | | $9$ | $7$ | $0$ | $10$ | | $10$ | $8$ | $0$ | $10$ | | $11$ | $9$ | $0$ | $30$ | | $12$ | $10$ | $0$ | $30$ | | $13$ | $12$ | $1$ | $30$ | | $14$ | $12$ | $2$ | $30$ | | $15$ | $15$ | $0$ | $15$ | | $16$ | $15$ | $1$ | $15$ | | $17$ | $15$ | $2$ | $15$ | | $18$ | $18$ | $0$ | $5$ | | $19$ | $18$ | $1$ | $5$ | | $20$ | $18$ | $2$ | $5$ | Translated by ChatGPT 5