Charcos de Lodo.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C#, C++, Java, Pascal, Python, VB

El Granjero Juan ha salido de su casa temprano a las 6 AM para el ordeño diario de Bessie. Sin embargo, en la tarde anterior el vio una fuerte lluvia, y los campos están algo enlodados. GJ comienza en el punto (0,0) en el plano de coordenadas y se dirige hacia Bessie quien está ubicada en el punto (X, Y) (-500 \leq X \leq 500; -500 \leq Y \leq 500). El puede ver N charcos de lodo, ubicados en los puntos (A_i, B_i) (-500 \leq A_i \leq 500; -500 \leq B_i \leq 500) del campo. Cada charco ocupa solo el punto en el que está. Habiendo comprado recientemente botas nuevas, el Granjero Juan no quiere absolutamente ensuciarlas parándose sobre lodo, pero quiere llegar a donde Bessie tan rápido como sea posible. A él ya se le hizo tarde debido a que él tuvo que contar todos los charcos. Si el Granjero Juan puede viajar únicamente paralelo a los ejes y girar en puntos con coordenadas enteras, ¿cuál es la distancia más corta que él debe viajar para llegar a donde Bessie y mantener limpias sus botas? Siempre existirá un camino sin lodo que el Granjero Juan pueda tomar para llegar a donde Bessie.

Entrada

• Línea 1: Tres enteros separados por espacio: X, Y, y N.

• Líneas 2… N+1: la línea i+1 contiene dos enteros separados por espacio.

Ejemplo de Entrada

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

Detalles de la Entrada

Bessie está en el punto (1, 2). El Granjero Juan ve 7 charcos de lodo; ubicados en los puntos: (0, 2); (-1, 3); (3, 1); (1, 1); (4, 2); (-1, 1); (2, 2). Gráficamente:

   4 . . . . . . . . 
   3 . M . . . . . . 
Y  2 . . M B M . M . 
   1 . M . M . M . . 
   0 . . * . . . . . 
  -1 . . . . . . . . 
    -2-1 0 1 2 3 4 5 
           X

Salida

• Línea 1: La distancia mínima que el Granjero Juan debe viajar para llegar a donde está Bessie sin parase en el lodo.

Ejemplo de Salida

11

Detalles de la Salida

El mejor camino para el Granjero Juan es (0, 0); (-1, 0); (-2, 0); (-2, 1); (-2, 2); (-2, 3); (-2, 4); (-1, 4); (0, 4); (0, 3); (1, 3); y (1,2), llegando finalmente a donde Bessie:

   4 ******* . . . . 
   3 * M . * . . . . 
Y  2 * . M B M . M . 
   1 * M . M . M . . 
   0 ***** . . . . . 
  -1 . . . . . . . . 
    -2-1 0 1 2 3 4 5 
           X

Comments

There are no comments at the moment.