Sparing w Programowaniu Zespołowym UAM & PP, 6.11.2004

Opis

Pan Jan - kupiec wiele podróżuje po całej Bajklolandii. W związku z jego ciekawą pracą ma bardzo wielu znajomych. Lecz pomimo tego, że zwiedza cały kraj rzadko widuje się z bratem Zbyszkiem. Jednak tuż przed swoją aktualną podróżą pan Jan dowiedział się że jego brat (mieszkający w Bajdocji) również wybiera się w podróż, więc postanowił, że postara się go spotkać w drodze. Tutaj jednak powstał problem - jak iść żeby się nie rozminąć z ukochanym bratem, a jednocześnie nie zwiększyć kosztów podróży?? I tutaj pojawia się szansa dla Ciebie - podrzędnego tragarza pana Jana. Pomóż mu rozwiązać ten problem a na pewno nie ominie Cię sowita nagroda. Z ukradkowych rozmów z szefem wiesz skąd i dokąd udajecie się wy oraz brat Zbyszek, a także wiesz ile czasu zajmie podróż bratu szefa. Wiedząc że obaj bracia chcą ponad wszystko zminimalizować koszt podróży (czyli będą podróżować najkrótsza z możliwych ścieżek - prosto do celu) postaraj się tak dobrać prędkość by umożliwić im spotkanie. Jeżeli taka prędkość nie istnieje to z przykrością będziesz musiał to także oznajmić.

Specyfikacja wejścia

W pierwszej linii wejścia znajdzie się liczba d - liczba testów. Każdy test będzie się składał z pojedynczej linii zawierającej 9 liczb całkowitych x1, y1, x2, y2, x3, y3, x4, y4, t, z zakresu (0,109) gdzie x1,y1,x2,y2 opisują trasę pana Jana; x3, y3, x4, y4 opisują trasę brata Zbyszka zaś t jest czasem jaki przewidział Zbyszek na podróż. Możesz założyć że obydwaj bracia podróżują ze stałą prędkością podczas całej podróży oraz że zawsze istnieje jednoznaczna odpowiedź.

Specyfikacja wyjścia

Dla każdego testu na wyjściu wypisz 3 liczby X,Y, v gdzie X,Y - jest spodziewanym punktem spotkania v - sugerowaną prędkością podróży pana Jana lub słowo "NIE" jeśli nie można tak dobrać prędkości by bracia się spotkali.

Przykład

2
1 2 2 4 5 4 6 2 2
2 1 2 3 1 2 5 2 4

NIE
2.00 2.00 1.00