W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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 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 oznaczająca liczbę zestawów testowych. Po niej następują zestawy w następującej postaci:
Pierwsza linia zestawu zawiera liczbę całkowitą () — liczbę drzew na terenie gry. W kolejnych liniach podane są pary liczb całkowitych , () – 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.
Dla danych wejściowych:
2 5 201 2 104 302 1 99 410 320 210 201 5 201 2 104 302 1 99 210 201 410 320
poprawną odpowiedzią jest:
NIE TAK
Autor zadania: (pomysł zapożyczony).