8829번 - Muzeum 다국어

Kapitan Pitt zwiedzając znane muzeum na każdym kroku napotykał na pilnujących cennych eksponatów strażników. Czy na pewno potrzeba ich aż tylu? Może wystarczyły jeden strażnik? Gdyby tylko dało się znaleźć odpowiednie miejsce... - myślał.

Plan muzeum jest wielokątem o wierzchołkach w punktach o naturalnych współrzędnych, każda krawędź ma długość 1, wszystkie kąty pomiędzy sąsiednimi ścianami są wielokrotnościami 90^o. 

Znając plan muzeum sprawdź, czy istnieje w nim miejsce ( o dowolnych, być może rzeczywistych współrzędnych), z którego widać każdy fragment muzeum.

W pierwszej linii znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ). Następnie opisywane są kolejne zestawy testowe.

Opis zestawu testowego zaczyna się od liczby naturalnej N ( 4 <= N <= 1000000 ) oznaczającej liczbę wierzchołków na planie muzeum.

W kolejnych N liniach opisywane są kolejne punkty wielokąta. Każdy z nich jest opisywany przez parę liczb naturalnych X_i Y_i ( 0 <= ( X_i, Y_i ) < 1000000 ), gdzie X_i oznacza pierwszą współrzędną punktu, a Y_i drugą.

Każde dwa kolejne punkty ( oraz pierwszy i ostatni ) są sąsiednimi wierzchołkami wielokąta reprezentującego plan muzeum.

Dla każdego zestawu testowego należy w osobnej linii wypisać "TAK", jeśli poszukiwane miejsce istnieje i "NIE" w przeciwnym przypadku.

• Wierzchołki wielokąta są wymienione w takiej kolejności, w jakiej można je napotkać obchodząc jego brzeg zgodnie albo przeciwnie do ruchu wskazówek zegara.
• Wielokąt reprezentuje konwencjonalne muzeum w którym ściany nie przecinają się ze sobą.
• Dwie sąsiednie ściany mogą tworzyć ze sobą kąt 180^o.