Saltos en el plano P35559


Statement
 

pdf   zip

thehtml

Se os dan n puntos {p1, …, pn} con coordenadas enteras en el plano, con pi = (xi, yi). 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 ps1, …, psm tal que si ∈ {1, …, n}, y para todo 1 ≤ i < m, se cumpla xsixsi+1 e ysiysi+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 106.

Salida

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

Puntuación

  • test-1:  ‍ Entradas donde n ≤ 5, todas las xi son diferentes entre si, y todas las yi 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 xi son diferentes entre si, y todas las yi son diferentes entre si.  ‍15 Puntos ‍
  • test-4:  ‍ Entradas donde n ≤ 200, como el Ejemplo 3.  ‍20 Puntos ‍
  • test-5:  ‍ Entradas donde n ≤ 104, todas las xi son diferentes entre si, y todas las yi son diferentes entre si.  ‍20 Puntos ‍
  • test-6:  ‍ Entradas donde n ≤ 104.  ‍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

    2
    0
    2
    2
    
  • Input

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

    Output

    4
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions