Ulice
Zadání
Bedřich je na návštěvě u Jiřího ve městě, kam se Jiří nedávno přestěhoval. Plánují, že než půjdou odpoledne do kina, Jiří proveze Bedřicha městem a ukáže mu všechny ulice. Ulice jsou dvojího druhu: Jedny směřují od západu na východ (budeme je nazývat ZV-ulice) a druhé směřují od jihu na sever (budeme je nazývat JS-ulice). Město, nebo přinejmenším jeho část, která je pro naší úlohu důležitá, má tvar obdélníka s N JS-ulicemi a M ZV-ulicemi. Jiřího dům stojí na rohu jedné z křižovatek a kino stojí na rohu jiné křižovatky.
Nezdá se ale, že by bylo účelné projíždět každou ulicí ve městě v celé její délce, proto Jiří volí následující strategii. V každé ulici ve městě projede vzdálenost alespoň jednoho bloku, to jest od jedné křižovatky na nejbližší, případně projede vzdálenost delší, nebude se ale v ulici obracet o vracet se po ní zpět. Každou ulici, jejíž část už projel, může později na některé z jejích křižovatek protnout, až bude projíždět ulicí kolmou na ní, nebude však do ní opět zabočovat a tedy ani už nepojede nějakým jiným jejím úsekem. Navíc, Jiří se během jízdy nechce vracet na startovní křižovatku a nechce přijet na cílovou křižovatku před skončením jízdy.
Situace je dále ještě nepatrně komplikována tím, že některé křižovatky ve městě jsou zcela neprůjezdné ze všech stran. Křižovatka u domu i u kina průjezdné jsou, lze tedy vyjet i případně dojet.
Jiří ví, že cesta od jedné křižovatky k sousední trvá vždy jednu minutu. Na to, aby dorazili z domu do kina, mají oba přátelé přesně T minut. Jiří chce tuto dobu vyčerpat celou, to jest nechce přijet ke kinu před vypršením této doby. Dobu nasedání a parkování apod zanedbáváme.
Předpokládáme, že ZV-ulice jsou číslovány od jihu počínaje 0 a JS-ulice jsou očíslovány od západu počínaje 0. Každá křižovatka má souřadnice [x, y], kde x udává číslo JS-ulice této křižovatky a y udává číslo ZV-ulice této křižovatky.
Úloha
Máme zjistit, zda lze z domu dorazit do kina v čase právě T při strategii popsané výše, a pokud to jde, určit počet různých cest z domu do kina. Dvě cesty považujeme za různé, pokud se liší alespoň v jednom projetém úseku v některé z ulic.
Vstup
Na vstupu jsou tři řádky. První řádek obsahuje šest čísel. První dvě čísla jsou N a M udávající rozměr města. Třetí a čtvrté číslo představují x-ovou a y-souřadnici křižovatky, kde cesta městem začíná. Páté a šesté číslo představují x-ovou a y-souřadnici křižovatky, kde stojí kino a kde cesta městem má skončit.
Druhý řádek obsahuje seznam neprůjezdných křižovatek. Nejprve je uveden počet těchto křižovatek a poté je pro každou z nich uvedena její x a y souřadnice. Pokud je seznam neprůjezdných křižovatek prázdný, druhý řádek obsahuje jediné číslo 0.
Třetí řádek obsahuje jediné číslo představující počet minut trvání jízdy z domu do kina. Všechna čísla na vstupu jsou celá a nezáporná, navzájem jsou na řádku oddělena jednou mezerou.
Můžeme předpokládat, že počet průjezdných křižovatek ve městě nepřesáhne 60.
Příklady
Příklad 1
3 3 0 0 2 0
0
84
Příklad 2
4 4 0 0 3 2
0
116
Příklad 3
4 4 0 0 3 2
1 2 2
112Tento příklad se od předchozího liší pouze jednou neprůjezdnou křižovatkou. image::old_practical_exams/ulice/pic21.svg[pic21, 130] image::old_practical_exams/ulice/pic22.svg[pic22, 130]