2959 - Enjoy Popping Balloons

Created by Carlos Joa Fong
Added by cjoa (2014-06-15)
Limits
Total Time: 10000 MS | Test Time: 6000 MS |Memory: 62 MB | Output: 64 MB | Size: 15 KB
Enabled languages
Available in

Description

Rafael has a strange hobby: he enjoys popping inflated balloons.

Rafael learned of the existence of a computer programming competition named ACM-ICPC, where participants receive some colorful balloons for solved problems. And at the end of the contest, the remaining balloons are given to staff members to take home. As his computer programming skills were weak, he volunteered as a staff member of the past ACM-ICPC Caribbean Finals, which were held at his local university.

At the end of the contest, Rafael managed to steal all remaining balloons and released them outside in the university square. To prevent them from floating away, he attached each balloon with a string tied to a nail on the ground.

From the rooftop of the building next to the university square, Rafael released a small remote-controlled drone. He controls the helicopter and runs it into the balloons. A balloon is popped when the dron flies into it. You may assume that the rooftop is higher than the height of any of the balloons.

To simplify, assume that each balloon is represented as a point in the X-Y plane, where the Y direction corresponds to height (y = 0 denotes the floor). The building runs along the Y-axis, so Rafael always releases the drone from a point on (0, H), where H is the height of the building.

For example, here is a side view of example 1. The horizontal line at h = 0 is the floor and the vertical line is the building. The "x" marks the rooftop from where Rafael releases his drone. There are 6 balloons located at: (4, 8), (7, 9), (13, 3), (13, 2), (23, 6), and (43, 8).



Due to a defect in its design, the drone can only go forward and/or downward, but never backward nor upward. For example, if the drone is currently at position (1, 9), it can only fly into (2, 9) or (1, 8). Furthermore, the drone is destroyed once it runs into the ground.

Given the positions of the balloons, determine the maximum number of balloons Rafael can pop with a single drone.
Rafael tiene un extraño pasatiempo: a él le encanta estallar globos inflados.

Rafael se enteró de la existencia de una competencia de programación de computadoras llamada ACM-ICPC, donde los participantes reciben coloridos globos por resolver ejercicios de computación. Al final de la competencia, los miembros del personal asistente de la competencia se llevan todos los globos que se quedaron sin entregarse. Como su habilidad de computación era débil, él se ofreció como voluntario para ser miembro del personal asistente de la pasada Final Caribeña del ACM-ICPC, la cual fue organizada en su universidad.

Al final de la competencia, Rafael logró quedarse con todos los globos restantes y los liberó en la plaza central de su universidad. Para prevenir que se escapen volando, él amarró, con un hilo, cada globo a un clavo en el suelo.

Desde el techo del edificio justo al lado de la plaza, Rafael liberó un pequeño dron, el cual él maneja con un control remoto para chocarlo contra los globos. Un globo estalla cuando el dron choca con éste. Se puede asumir que el techo del edificio donde libera el dron es más alto que la altura de cualquiera de los globos.

Para simplificar, asume que cada globo es representado como un punto en el plano cartesiano, donde la dirección Y corresponde a la altura (y = 0 indica el suelo). El edificio se encuentra en el mismo eje Y, por lo tanto Rafael siempre libera su dron desde la posición (0, H), donde H es la altura del edificio.

Por ejemplo, la imagen debajo muestra una vista lateral del ejemplo 1. La línea horizontal en h = 0 es el piso y la línea vertical es el edificio. La "x" marca el techo desde donde Rafael libera su dron. Tenemos 6 globos localizados en las posiciones: (4, 8), (7, 9), (13, 3), (13, 2), (23, 6) y (43, 8).



Debido a un defecto en su diseño, el dron sólo puede avanzar hacia adelante y/o hacia abajo, pero nunca hacia atrás ni hacia arriba. Por ejemplo, si su posición actual es (1, 9), el dron solo puede llegar a (2, 9) ó (1, 8). En adición, el dron se destruye una vez que choca contra el suelo.

Dadas las posiciones de los globos, determina la máxima cantidad de globos que Rafael puede estallar usando únicamente un dron.
Rafael has a strange hobby: he enjoys popping inflated balloons.

Rafael learned of the existence of a computer programming competition named ACM-ICPC, where participants receive some colorful balloons for solved problems. And at the end of the contest, the remaining balloons are given to staff members to take home. As his computer programming skills were weak, he volunteered as a staff member of the past ACM-ICPC Caribbean Finals, which were held at his local university.

At the end of the contest, Rafael managed to steal all remaining balloons and released them outside in the university square. To prevent them from floating away, he attached each balloon with a string tied to a nail on the ground.

From the rooftop of the building next to the university square, Rafael released a small remote-controlled drone. He controls the helicopter and runs it into the balloons. A balloon is popped when the dron flies into it. You may assume that the rooftop is higher than the height of any of the balloons.

To simplify, assume that each balloon is represented as a point in the X-Y plane, where the Y direction corresponds to height (y = 0 denotes the floor). The building runs along the Y-axis, so Rafael always releases the drone from a point on (0, H), where H is the height of the building.

For example, here is a side view of example 1. The horizontal line at h = 0 is the floor and the vertical line is the building. The "x" marks the rooftop from where Rafael releases his drone. There are 6 balloons located at: (4, 8), (7, 9), (13, 3), (13, 2), (23, 6), and (43, 8).



Due to a defect in its design, the drone can only go forward and/or downward, but never backward nor upward. For example, if the drone is currently at position (1, 9), it can only fly into (2, 9) or (1, 8). Furthermore, the drone is destroyed once it runs into the ground.

Given the positions of the balloons, determine the maximum number of balloons Rafael can pop with a single drone.

Input specification

The first line of input consists of an integer T (1 <= T <= 100) denoting the number of test cases. Each test case starts with an empty line, followed by a line containing a single integer N (1 <= N <= 10^5) representing the number of balloons released in the university square. Each of the next N lines consists of two space-separated integers X and Y (1 <= X, Y <= 10^6) corresponding to the coordinates of each balloon. You can safely assume that no two balloons occupy the same position. The sum of N over all test cases is at most 10^6.
La primera línea de entrada consiste en un número entero T (1 <= T <= 100), el cual indica la cantidad de casos de pruebas a procesar. Cada caso de prueba empieza con una línea en blanco, seguido de una línea conteniendo un único número entero N (1 <= N <= 10^5) que representa la cantidad de globos liberados en la plaza de la universidad. Cada una de las siguientes N líneas consiste en dos números enteros X e Y (1 <= X, Y <= 10^6), los cuales corresponden a las coordenadas de cada globo. Usted puede asumir con seguridad que las posiciones de los globos son distintas. La suma de las N de todos los casos de pruebas no excede 10^6.
The first line of input consists of an integer T (1 <= T <= 100) denoting the number of test cases. Each test case starts with an empty line, followed by a line containing a single integer N (1 <= N <= 10^5) representing the number of balloons released in the university square. Each of the next N lines consists of two space-separated integers X and Y (1 <= X, Y <= 10^6) corresponding to the coordinates of each balloon. You can safely assume that no two balloons occupy the same position. The sum of N over all test cases is at most 10^6.

Output specification

For each test case output a line with the corresponding answer.
Por cada caso usted debe imprimir una línea con la respuesta correspondiente.
The first line of input consists of an integer T (1 <= T <= 100) denoting the number of test cases. Each test case starts with an empty line, followed by a line containing a single integer N (1 <= N <= 10^5) representing the number of balloons released in the university square. Each of the next N lines consists of two space-separated integers X and Y (1 <= X, Y <= 10^6) corresponding to the coordinates of each balloon. You can safely assume that no two balloons occupy the same position. The sum of N over all test cases is at most 10^6.

Sample input

2

6
4 8
7 9
13 3
13 2
23 6
43 8

4
1 3
2 2
2 3
3 2

Sample output

3
4

Hint(s)