== include(page="template/taskheader" task_id="gropi") ==
Datorita rezultatelor foarte bune pe care le obtinuse la Olimpiada Balcanica pentru Juniori in urma cu 5 ani, Danut primeste de la parintii sai o masina noua (nu de jucarie). Pentru ca e doritor sa o testeze, el hotaraste sa faca diferite trasee prin oras. Orasul lui Danut poate fi considerat, pentru simplitate, o matrice cu $2$ linii si $C$ coloane. Deoarece orasul este unul in curs de dezvoltare, este deocamdata plin de gropi. Danut stie dinainte harta orasului: stie care dintre zonele din oras sunt bune, si care sunt pline de gropi. El nu vrea sa isi strice masina si de aceea nu va trece niciodata printr-o zona cu gropi. Danut are de gand sa faca $M$ trasee intre zone cunoscute din oras si se intreaba, pentru fiecare din aceste $M$ trasee pe care le planuieste, care este timpul minim in care poate fi parcurs, astfel incat zonele cu gropi sa fie ocolite. Se stie ca durata de deplasare printr-o zona fara gropi a orasului dureaza exact $1$ minut (Danut pastreaza viteza constanta la $50$ km/h).
Poveste si cerinta...
h2. Date de intrare
Fisierul de intrare $gropi.in$ contine pe prima linie doua numere naturale, {$C$}, care reprezinta numarul de coloane din reprezentarea schematica a orasului, si {$N$}, numarul de zone din oras care au gropi si trebuie ocolite. Pe fiecare din urmatoarele $N$ linii se gaseste cate o pereche de numere naturale {$(x y)$}, care reprezinta coordonatele unei zone cu gropi. Urmatoarea linie contine numarul {$M$}, numarul de trasee pe care le efectueaza Danut. Fisierul contine apoi $M$ linii, pe fiecare aflandu-se cate patru numere naturale, {$(x{~1~} y{~1~} x{~2~} y{~2~})$}, cu semnificatia ca Danut doreste sa plece cu masina de la zona de coordonate {$(x{~1~} y{~1~})$} si sa ajunga la zona de coordonate {$(x{~2~} y{~2~})$}.
Fisierul de intrare $gropi.in$ ...
h2. Date de iesire
In fisierul de iesire $gropi.out$ se vor afla exact $M$ numere naturale. FIecare linie contine durata minima a traseului corespunzator din fisierul de intrare.
In fisierul de iesire $gropi.out$ ...
h2. Restrictii
* $1 ≤ N ≤ minim(100 000, 2*C)$
* $1 ≤ M ≤ 100 000$
* $2 ≤ C ≤ 2 000 000 000$
* Pentru 50% din teste, $C ≤ 250$ si $M ≤ 200$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. gropi.in |_. gropi.out |
|10 4
1 3
2 9
1 7
1 5
2
1 1 1 6
1 9 2 1
|8
10
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
Orasul arata astfel:
!problema/gropi?oras.jpg!
...
== include(page="template/taskfooter" task_id="gropi") ==
