Programozás‎ > ‎Feladatok‎ > ‎

Menekülés

Hadifoglyok egy csoportja el akar szökni a börtönből. A szökést (az A-val jelölt börtönből) nagyon jól megszervezték, de most el kell jutniuk a B-vel jelölt faluba. Sajnos a börtön és a falu között csak egy szűk kanyonban lehet haladni, amit őrök felügyelnek. Az őrök egy helyben állnak és 100 méter távolságig látnak el. A menekülés útvonala akkor biztonságos, hogy bármely pillanatban bármely őrtől 100 méternél nagyobb távolságra haladnak a rabok.
Ismerjük a kanyon szélességét és hosszát, továbbá az őrök pontos pozícióját. A menekülők már elég erőszakos cselekményt láttak, ezért szeretnék minimalizálni azon őrök számát, akiket "ki kell iktatni" a biztonságos meneküléshez. Azok az őrök is biztonságosan "kiiktathatók", akiket esetleg lát egy másik őr. 
 

Feladat

Írjunk programot, ami megadja, hogy legkesebb hány őr "kiiktatása" kell a meneküléshez.

Bemenet

Az első sorban L, W, és N található, a kanyon hossza, szélessége és az őrök száma. Ezután N pár következik, az őrök koordinátái  (0 ≤ Xi ≤ L, 0 ≤ Yi ≤ W). A koordináták méterben vannak megadva, az ábrán látható a koordináta-rendszer elhelyezkedése. Az A és B pontoknak csak az X koordinátáit ismerjük: 0 és L.

Méretek

1 ≤ W ≤ 50,000 1 ≤ L ≤ 50,000 1 ≤ N ≤ 250

Kimenet

A kimenet egyetlen számot tartalmaz, a "kiiktatandó" őrök minimális számát. Ha alapból is biztonságosan ki lehet jutni, akkor 0-át kell írni.

Példa

Bemenet  Kimenet
130 340 5
10 50
130 130
70 170
0 180
60 260
1


Tesztadatok

Címkék

Algoritmusok: 

megoldás