Fișierul intrare/ieșire	turist.in, turist.out	Sursă	OJI 2008 clasa a 8-a
Autor		Adăugată de	Tudor Coman • tudorcoman
Timp de execuție pe test	0.1 sec	Limită de memorie	1024 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Turist (clasa a 8-a)

Harta unui continent poate fi văzută ca un dreptunghi având înălțimea de M unități, iar lățimea de N unități. Colțul din stânga sus al hărții are coordonatele (0,0), iar colțul din dreapta jos are coordonatele (M,N). Coordonatele orașelor de pe hartă sunt întotdeauna numere întregi, adică sunt de forma (l,c) cu 0≤l≤M, reprezentând linia și 0≤c≤N, reprezentând coloana. În unul din orașele de pe hartă se găsește un turist. El dorește să pornească într-o expediție deosebită. A decis să plece într-o anumită direcție, și să păstreze aceea direcție pănă ajunge la marginea continentului (a hărții) unde se încheie expediția sa. Dorește însă să aleagă acea direcție care îl asigură că pe drumul său va trece prin cât mai multe orașe.

Cerință

Dându-se dimensiunile hărții, coordonatele orașului în care se găsește turistul și coordonatele tuturor celorlalte orașe de pe hartă, se cere să se determine numărul maxim de orașe pe care le va vizita turistul.

Date de intrare

Pe prima linie a fișierului de intrare turist.in se găsesc numerele naturale M N separate printr-un spațiu reprezentând dimensiunile hărții. A doua linie a fișierului conține două numere naturale l și c separate printr-un spațiu, reprezentând poziția inițială a turistului pe hartă. Linia a treia a fișierului conține un număr natural k, reprezentând numărul de orașele de pe hartă, diferite de orașul în care se găsește turistul.
Pe următoarele k linii se găsesc câte două numere naturale, separate printr-un spațiu, reprezentând coordonatele câte unui oraș de pe hartă, altele decât cel în care se găsește turistul.

Date de ieșire

Fișierul de ieșire turist.out va avea pe prima sa linie, un număr natural reprezentând numărul maxim de orașe pe care le vizitează turistul.

Restricții

• 1 ≤ M, N ≤ 1000
• 1 ≤ k ≤ 2000

Exemplu

turist.in	turist.out	Explicații
5 10 3 2 7 0 0 0 8 1 6 2 2 2 4 3 7 4 5	3	Datele de intrare corespund hărții din figura următoare. Traseul ales este cel indicat de linia trasată.