== include(page="template/taskheader" task_id="noxa") ==
!>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 Euro 3, iar într-o bună zi Gabi Fii Rea, primărița orașului Noxa, a interzis toate mașinile Euro 3.
Codoi s-a trezit pentru prima oară î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.
Î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*.
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).
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
În fișierul de intrare $noxa.in$ se află, pe prima linie, *M* și *N*, numărul de pătrate pe linie, respectiv pe coloană î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.
Î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$ 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.
Î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_
* 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") ==
