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.|

MWP3_2E1 - Pył

Jan, główny bohater tegorocznych zawodów, po licznych przygodach postanowił w końcu odpocząć. Będąc już doświadczonym i bogatym programistą wybrał egzotyczne wyspy na Oceanie Spokojnym. Jak powszechnie wiadomo wszystko co dobre szybko się kończy. Niestety, stwierdzenie to okazało się prawdziwe również dla naszego bohatera. Nie dość, że szef kazał mu wracać do firmy w połowie urlopu to na dodatek wybuch wulkanu sprawił, że większość samolotów nie kursuje zgodnie z rozkładem (nad częścią terenów unosi się wulkaniczny pył). Szefa nie interesują żadne wymówki, Jan ma "coś" zrobić, aby jutro rano stawić się w pracy. Nasz bohater, zdesperowany, udał się na najbliższe lotnisko, gdzie usłyszał - Nie ma problemu, samolot poleci o ile to tylko możliwe i o ile wyznaczy nam Pan trasę lotu. - Nic prostszego - pomyślał Jan i zabrał się do czytania map pogodowych. Spisał współrzędne wierzchołków figury jaką tworzy chmura pyłu, punktów startu i lądowania i zaczął pisać program. Kto wie, może i Ty będziesz kiedyś w podobnej sytuacji? Lepiej mieć już taki program gotowy!

Na podstawie współrzędnych punktów startu i lądowania oraz wierzchołków figury jaką tworzy chmura pyłu ustal czy powrót Jana do pracy jest możliwy. Jeżeli jest on możliwy podaj długość najkrótszej dopuszczalnej trasy. Dla ułatwienia zakładamy, że pył rozchodzi się dosyć regularnie dzięki czemu zawsze tworzy wielokąt wypukły. Zakładamy również, że możemy przelecieć wzdłuż krawędzi wielokąta określającego chmurę pyłu wulkanicznego. Niestety, ze względu na tzw. kołowanie jakie samoloty muszą wykonywać w pobliżu lotnisk w przypadku, gdy którekolwiek z nich znajduje się dokładnie na obrzeżach chmury uznajemy, że lot nie może się odbyć.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 100) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajdują się cztery liczby całkowite X1, Y1, X2, Y2 (-109X1, Y1, X2, Y2 ≤ 109) oznaczają one odpowiednio: współrzędne lotniska początkowego i końcowego. W drugiej linii znajduje się jedna liczba naturalna n oznaczająca ilość punktów określających wielokąt stworzony przez chmurę pyłu. W kolejnych n liniach znajdują się, dwie liczby całkowite, współrzędne X, Y tych punktów (-109X, Y ≤ 109). Otrzymywane na wejściu wierzchołki posortowane są zgodnie z ruchem wskazówek zegara począwszy od pierwszego wczytanego wierzchołka. Współrzędne każdego z wierzchołków oraz obydwu lotnisk są zawsze liczbami całkowitymi.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać słowo "NIE" jeśli powrót Jana do pracy nie jest możliwy albo długość najkrótszej trasy powrotnej w przeciwnym przypadku. Długość trasy należy wypisać z dokładnością do trzech miejsc po przecinku.

Przykład

Wejście:

3
13 4 7 4
5
5 4
6 7
10 6
9 2
6 2
13 4 4 2
5
5 4
6 7
10 6
9 2
6 2
13 4 4 1
5
5 4
6 7
10 6
9 2
6 2

Wyjście:

NIE
9.472
9.571

Dodane przez:Maciej Boniecki
Data dodania:2010-12-11
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:III Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.