Fişierul intrare/ieşire:noxa.in, noxa.outSursătimus.ru
AutorLeonid VolkovAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie10240 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Noxa (clasa a 7-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!

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).

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.

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.

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

Exemplu

noxa.innoxa.outExplicaţie
3 2
3
1 1
3 2
1 2
382
Vezi imaginea. Avem o grilă de M=3 coloane şi N=2 linii. 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(1002 + 1002) + 100 = 382.842712475...
 
Veţi afişa doar partea întreagă a acestui număr, adică 382.
Trebuie sa te autentifici pentru a trimite solutii. Click aici