8450번 - Ninja 다국어

Dwóch mistrzów ninja, Takeshi Bajtanamura i Matsuo Bitezuki, postanowiło zmierzyć się w zawodach w byciu niewidocznym. Teren rozgrywki to duży las (który będziemy traktować jak płaszczyznę euklidesową), w którym rośnie n drzew (punktowych, rzecz jasna). Ninja będą przemykać od drzewa do drzewa po liniach prostych, pozostając oczywiście ukrytymi przed oczyma postronnych (schowanie się za punktowym drzewem nie jest dla mistrza żadnym wyzwaniem). Każdy z mistrzów ma przypisane drzewo startowe, w którym rozpoczyna, i drzewo, do którego musi dotrzeć.

Twoim zadaniem jest wyznaczenie tras mistrzów. Każda z nich musi być zgodna z regułami gry (czyli być łamaną, której wierzchołkami są niektóre drzewa). Trasy mistrzów nie mogą się krzyżować, ani mieć żadnych punktów wspólnych — to jeszcze nie czas na ostateczną konfrontację!

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita T oznaczająca liczbę zestawów testowych. Po niej następują zestawy w następującej postaci:

Pierwsza linia zestawu zawiera liczbę całkowitą n (4 ≤ n ≤ 60 000) — liczbę drzew na terenie gry. W kolejnych n liniach podane są pary liczb całkowitych x, y (0 ≤ x, y ≤ 10⁹) – współrzędne kolejnych drzew. Pierwsze i drugie z kolei drzewo to odpowiednio początek i koniec drogi pierwszego mistrza, trzecie i czwarte — drugiego mistrza. Możesz założyć, że żadne dwa drzewa nie rosną w tym samym miejscu oraz żadne trzy drzewa nie leżą na jednej prostej.

Dla każdego zestawu należy wypisać w osobnej linii słowo TAK, jeśli można wytyczyć drogi mistrzów, NIE, jeśli jest to niemożliwe.