Problem Background

NOIP2016 Senior Group D2T3

Problem Description

Kiana has recently become obsessed with a magical game.

In essence, the game takes place on a plane.

A slingshot is located at $(0,0)$, and Kiana can use it to launch a red bird into the first quadrant. The flight path of each bird follows a curve of the form $y = ax^2 + bx$, where $a$ and $b$ are parameters specified by Kiana, and must satisfy $a < 0$, with $a$ and $b$ being real numbers.

When a bird returns to the ground (i.e., the $x$-axis), it instantly disappears.

In a particular level of the game, there are $n$ green pigs in the first quadrant, with the $i$-th pig located at coordinates $\left(x_i, y_i\right)$.

If the flight path of a bird passes through $\left(x_i, y_i\right)$, the $i$-th pig is eliminated, and the bird will continue to fly along its original path.

If a bird's flight path does not pass through $\left(x_i, y_i\right)$, the bird's entire flight will have no effect on the $i$-th pig.

For example, if two pigs are located at $(1,3)$ and $(3,3)$, Kiana can choose to launch a bird with a flight path of $y = -x^2 + 4x$, which will eliminate both pigs.

The objective of the game is to eliminate all the pigs by launching birds.

Each level of this magical game is challenging for Kiana, so she inputs some mysterious commands to make the game easier. These commands are detailed in the Input Format section.

Assuming there are $T$ levels in the game, Kiana wants to know, for each level, the minimum number of birds needed to eliminate all the pigs. Since she can't calculate this herself, she hopes you can tell her.

Input Format

The first line contains a positive integer $T$, representing the total number of levels in the game.

The following sections describe the information for these $T$ levels. Each level starts with a line containing two non-negative integers $n$ and $m$, representing the number of pigs in the level and the type of mysterious command Kiana inputs. The next $n$ lines contain two positive real numbers $x_i$ and $y_i$, indicating the coordinates of the $i$-th pig. It is guaranteed that no two pigs in the same level have the same coordinates.

If $m = 0$, it means Kiana inputs a command with no effect.

If $m = 1$, the level will satisfy: At most $\lceil n/3 + 1 \rceil$ birds are needed to eliminate all the pigs.

If $m = 2$, the level will satisfy: There is always an optimal solution where one bird eliminates at least $\lfloor n/3 \rfloor$ pigs.

It is guaranteed that $1 \leq n \leq 18$, $0 \leq m \leq 2$, $0 < x_i, y_i < 10$, and all real numbers in the input are rounded to two decimal places.

In the above text, $\lceil c \rceil$ and $\lfloor c \rfloor$ denote the ceiling and floor functions applied to $c$, respectively, such as $\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$.

Output Format

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

Sample Input and Output

Sample Input #1

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

Sample Output #1

1
1

Sample Input #2

3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00

Sample Output #2

2
2
3

Sample Input #3

1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99

Sample Output #3

6

Notes

Sample Explanation 1

This set of data contains two levels.

The first level is the same as described in the Problem Description, with two pigs located at $(1.00, 3.00)$ and $(3.00, 3.00)$. Launching one bird with a flight path of $y = -x^2 + 4x$ will eliminate both pigs.

In the second level, there are five pigs, but upon observation, we can see that their coordinates all lie on the parabola $y = -x^2 + 6x$, so Kiana only needs to launch one bird to eliminate all the pigs.

Data Range

见题面 Input 部分

见题面 Output 部分