Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_20_14 - Diament

Diament

Jasiu, znany specjalista od zabezpieczeń bankowych, ma dziś nie lada kłopot. Otóż nie pamięta hasła, dzięki któremu może wyłączyć laserowy system w bardzo ważnym pomieszczeniu. To pomieszczenie jest szczególnie chronione, znajduje się tam bowiem diament Hope. Jedyny sposób, aby wyłączyć system i wprowadzić nowe hasło, to dostać się do diamentu, pod którym znajduję się wyłącznik. Wygląda na to, że Jasiu będzie musiał czołgać się lub przeskakiwać wiązki laserowe. Wiadomo, że w każdym takim pomieszczeniu z diamentem, wyznaczono kwadrat o długości n, którego lewy dolny wierzchołek ma współrzędne (0,0), a prawy górny ma współrzędne (n, n). Na brzegu tego kwadratu znajdują się punkty o współrzędnych całkowitych, niektóre z tych punktów połączone są wiązkami laserowymi, które chronią cenny diament. Wiązkami laserowymi połączone są także sąsiednie wierzchołki kwadratu. Jasiu ma wszystkie informacje o wiązkach i położeniu diamentu, chce zminimalizować ryzyko włączenia alarmu, pokonując jak najmniej takich wiązek. Pomóż Jasiowi i napisz program, który wyznaczy najmniejszą liczbę promieni laserowych, jakie będzie musiał pokonać w drodze do diamentu, być może będzie z niego nie raz jeszcze korzystał. Jasiu zdradza dodatkowo, że nie istnieje punkt należący do kwadratu, w którym przecinają się więcej niż dwie wiązki laserowe, żadne dwie wiązki nie nakładają się oraz żadna wiązka nie przechodzi przez punkt diamentu. Ponadto wiadomo, że Jasiu jest tak chudy, że potrafi przecisnąć się przez jakąkolwiek niezerową odległość między dwoma punktami.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 100). Dalej podane są przypadki testowe. Pierwszy wiersz każdego przypadku zawiera cztery liczby n, m, x, y (4 ≤ n ≤ 100, 0 ≤ m ≤ 2(n-1), 0 < x,y < n), gdzie n to liczba całkowita oznaczająca rozmiar kwadratu, m to liczba promieni laserowych przecinających wnętrze kwadratu, a x, y to współrzędne rzeczywiste, podane z dokładnością do dwóch miejsc po przecinku, wyznaczające położenie diamentu. W kolejnych m wierszach podane są po cztery liczby całkowite x1, y1, x2, y2 należące do brzegu kwadratu i oznaczające współrzędne początku i końca wiązki laserowej.

Wyjście
Dla każdego przypadku testowego należy wypisać najmniejszą liczbę promieni laserowych, które musi pokonać Jasiu, aby dotrzeć do diamentu.

Przykład

Wejście
1
6 7 3.00 3.00
1 0 0 5
2 0 6 4
3 0 1 6
4 0 4 6
5 0 0 3
0 4 5 6
2 6 6 2

Wyjście
2

Rysunek do przykładu.


Dodane przez:Mariusz Śliwiński
Data dodania:2014-12-24
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.