Harta unui continent poate fi văzută ca un dreptunghi având înălţimea de unităţi, iar lăţimea de unităţi. Colţul din stânga sus al hărţii are coordonatele (), iar colţul din dreapta jos are coordonatele (). Coordonatele oraşelor de pe hartă sunt întotdeauna numere întregi, adică sunt de forma () cu , reprezentând linia şi , 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 separate printr-un spaţiu reprezentând dimensiunile hărţii. A doua linie a fişierului conţine două numere naturale şi 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 , reprezentând numărul de oraşele de pe hartă, diferite de oraşul în care se găseşte turistul.
Pe următoarele 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 și precizări
- ;
- ;
Exemplu
turist.in
5 10
3 2
7
0 0
0 8
1 6
2 2
2 4
3 7
4 5
turist.out
3
Explicație
Imaginea de mai jos corespunde cu datele de intrare din exemplu.
