== include(page="template/taskheader" task_id="noxa") ==
Poveste și cerință...
!>problema/noxa?noxa.png!
În orașul *Noxa* toți locuitorii sînt mîndri că ei merg doar cu mașinile lor personale. Sub președintele *Trăiam Binescu* nivelul de trai a crescut simțitor, astfel încît orice noxian are cel puțin două mașini. *Codoi*, cetățean model, conducea mașina zilnic pînă la serviciu și înapoi. Dar vai, mașina lui era *Eurău 3*, iar într-o bună zi *Gabi Fii Rea*, primărița orașului *Noxa*, a interzis toate mașinile *Eurău 3*. *Codoi* s-a trezit pentru prima oară în viață în situația de a ajunge la serviciu pe jos. Era pierdut! Nu recunoștea nimic din orașul său. Era prima oară pieton în *Noxa*. Mai mult, aerul era irespirabil: particule, mono/dioxid de carbon, oxid de azot. Trebuia să meargă rapid sau risca să-și piardă cunoștința, poate și viața!
h2. Cerință
Ajutați-l pe *Codoi* să ajungă la serviciu pe *drumul cel mai scurt*.
Orașul *Noxa* este format din străzi paralele și perpendiculare, ce formează o grilă de pătrate identice, cu *latura de 100m*. Apartamentul lui *Codoi* se află în colțul din stînga sus, iar serviciul lui se află în colțul din dreapta-jos, la *M* pătrate, respectiv *N* pătrate distanță. Unele pătrate sînt *parcuri*. Ele pot fi traversate pe diagonală, în direcția jos-dreapta (convenabil).
h2. Date de intrare
Fișierul de intrare $noxa.in$ ...
În fișierul de intrare $noxa.in$ se află, pe prima linie, *M* și *N*, numărul de pătrate pe linii, respectiv pe coloane între apartamentul lui *Codoi* și serviciu. Pe următoarea linie se află *K*, numărul de parcuri. Pe următoarele *K* linii se află liniile și coloanele celor *K* parcuri, în numerotare de la 1.
h2. Date de ieșire
În fișierul de ieșire $noxa.out$ ...
În fișierul de ieșire $noxa.out$ veți scrie un singur număr, anume lungimea, în metri, a drumului cel mai scurt pe care să îl urmeze *Codoi*. Deoarece lungimea este un număr cu zecimale, veți afișa doar partea întreagă a acelui număr.
h2. Restricții
* $... ≤ ... ≤ ...$
* 0 ≤ *M*, *N* ≤ 10000
* 0 ≤ *K* ≤ 1000
* Pentru teste în valoare de 75p [*M*]·[*N*] ≤ 10 milioane
* latura unui pătrat din grilă este de 100m
* funcția _sqrt(x)_ returnează un număr real, care înmulțit cu un număr întreg are ca rezultat tot un număr real
* trunchierea unui număr real _x_ la întreg se face astfel: @(int)x@
h2. Exemplu
table(example).
|_. noxa.in |_. noxa.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
table(example).
|_. noxa.in |_. noxa.out |_. Explicație |
| 3 2
3
1 1
3 2
1 2
| 382
| Vezi imaginea. Avem o grilă de [*M*]=3 linii și [*N*]=2 coloane. Există și trei parcuri ce pot fi
traversate diagonal, ca în figură, la coordonatele (1 1), (1 2) și (3 2). Cel mai scurt drum este
marcat cu roșu și este egal cu lungimea a două diagonale, plus un drum vertical:
2·sqrt(100[^2^] + 100[^2^]) + 100 = 382.842712475...
Veți afișa doar partea întreagă a acestui număr, adică 382.
|
== include(page="template/taskfooter" task_id="noxa") ==
