Saltos en el plano P35559

Statement

html

Se os dan n puntos {p₁, …, p_n} con coordenadas enteras en el plano, con p_i = (x_i, y_i). Vuestra tarea es calcular el máximo número de saltos que se pueden realizar entre esos puntos, de manera que en ningún salto se decrementen ni la coordenada x ni la y. Es decir, hay que calcular una secuencia de tamaño máximo de puntos diferentes p_s₁, …, p_{s_m} tal que s_i ∈ {1, …, n}, y para todo 1 ≤ i < m, se cumpla x_{s_i} ≤ x_{s_i+1} e y_{s_i} ≤ y_{s_i+1}.

Por ejemplo, si la colección de puntos es {(1, 4), (3, 1), (5, 2), (5, 3), (7, 1), (7, 3), (8, 4) }, se pueden conseguir cuatro saltos, como esta figura demuestra:

unit=0.1cm

(100,60) linestyle=dotted linewidth=1.2pt linecolor=green

(00,20)(90,20) (00,30)(90,30) (00,40)(90,40) (00,50)(90,50) (00,60)(90,60) (10,10)(10,60) (20,10)(20,60) (30,10)(30,60) (40,10)(40,60) (50,10)(50,60) (60,10)(60,60) (70,10)(70,60) (80,10)(80,60) (90,10)(90,60)

linestyle=solid linewidth=2pt linecolor=black ->(00,10)(90,10) ->(00,10)(00,60)

(10,04)1 (20,04)2 (30,04)3 (40,04)4 (50,04)5 (60,04)6 (70,04)7 (80,04)8

(-5,20)1 (-5,30)2 (-5,40)3 (-5,50)4

linecolor=blue

(30,20)(50,30) (50,30)(50,40) (50,40)(70,40) (70,40)(80,50)

linestyle=solid linewidth=2pt linecolor=red fillcolor=red

(10,50)2 (30,20)2 (50,30)2 (50,40)2 (70,20)2 (70,40)2 (80,50)2

linestyle=solid linewidth=2pt linecolor=black fillcolor=black

Entrada

La entrada consiste en diversos casos, cada uno con n, seguida de n puntos diferentes. Podéis asumir n ≥ 1, y que el valor absoluto de cada coordenada es como mucho 10⁶.

Salida

Para cada caso, escribid el máximo número de saltos posibles.

Puntuación

test-1: Entradas donde n ≤ 5, todas las x_i son diferentes entre si, y todas las y_i son diferentes entre si, como el Ejemplo 1. 5 Puntos

test-2: Entradas donde n ≤ 5, como el Ejemplo 2. 10 Puntos

test-3: Entradas donde n ≤ 200, todas las x_i son diferentes entre si, y todas las y_i son diferentes entre si. 15 Puntos

test-4: Entradas donde n ≤ 200, como el Ejemplo 3. 20 Puntos

test-5: Entradas donde n ≤ 10⁴, todas las x_i son diferentes entre si, y todas las y_i son diferentes entre si. 20 Puntos

test-6: Entradas donde n ≤ 10⁴. 30 Puntos

Public test cases

Input

1  3 3
2  1 -2  -1 1
2  0 0  -1 -1

Output

0
0
1

Input

3  0 0  -2 -2  -1 -1
3  2 0  1 1  0 2
3  0 0  0 1  0 2
3  0 0  -1 0  -2 0

Output

Input

7  1 4  3 1  5 2  5 3  7 1  7 3  8 4

Output

Information

Author: Salvador Roura
Language: Spanish
Official solutions: C++
User solutions