Gobeliny

Limit pamięci: 128 MB

W Bajtockim Muzeum Sztuk Pięknych rozpoczyna się wystawa gobelinów. Główna sala wystawowa ma, patrząc z góry, kształt wielokąta (niekoniecznie wypukłego). Na każdej ze ścian sali powieszono jeden gobelin. Każdy gobelin zajmuje dokładnie całą powierzchnię ściany.

Do sali wstawiono lampę, która ma oświetlać wystawę. Lampa świeci równomiernie we wszystkich kierunkach. Wiadomo, że niektóre z gobelinów muszą być dobrze oświetlone, a niektórych - wręcz przeciwnie - nie można wystawiać na ostre światło.

Bajtazar, kustosz muzeum, zaczął przesuwać lampę po sali, ale nie udało mu się jej ustawić tak, żeby był zadowolony. Bajtazar jest przerażony - obawia się, że będzie trzeba przewieszać gobeliny (co wymaga dużo pracy), a do otwarcia wystawy zostało bardzo niewiele czasu. Może zdołasz mu pomóc i podpowiesz, czy jego wysiłki w ogóle mają sens?

Twoim zadaniem jest rozstrzygnięcie, czy istnieje położenie lampy spełniające poniższe warunki:

• każda ściana musi być albo oświetlona w całości, albo zaciemniona w całości, w zależności od wymagań dotyczących danego gobelinu; natomiast nie może istnieć ściana, na której część pada światło, a na część nie;
• jeżeli lampa znajduje się dokładnie w linii ściany, to jej nie oświetla;
• lampy nie można wyłączyć ani zabrać z sali; musi być włączona i znajdować się wewnątrz sali (w szczególności nie może znajdować się na żadnej ze ścian ani w rogu sali).

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę zestawów danych. W kolejnych wierszach znajdują się opisy zestawów danych.

W pierwszym wierszu opisu znajduje się jedna liczba całkowita (), oznaczająca liczbę ścian sali wystawowej. W kolejnych wierszach opisany jest kształt sali. W każdym z tych wierszy znajdują się dwie liczby całkowite i oddzielone pojedynczym odstępem ( dla ) - są to współrzędne narożnika sali, czyli wierzchołka wielokąta opisującego kształt sali. Wierzchołki są podane w kolejności zgodnej z kierunkiem ruchu wskazówek zegara.

W kolejnych wierszach opisane są wymagania dotyczące gobelinów wiszących na ścianach. W każdym z tych wierszy znajduje się jedna litera S lub C, oznaczająca odpowiednio, że ściana ma być oświetlona lub zaciemniona. Litera znajdująca się w -tym z tych wierszy (dla ) dotyczy ściany łączącej wierzchołki -ty oraz -szy. Litera znajdująca się w ostatnim z tych wierszy dotyczy ściany łączącej ostatni wierzchołek z pierwszym.

Wielokąt opisujący kształt sali nie ma samoprzecięć, tzn. poza sąsiednimi bokami, które siłą rzeczy mają wspólny koniec, żadne dwa boki wielokąta nie mają punktów wspólnych. Żadne trzy wierzchołki wielokąta nie są współliniowe.

W testach wartych łącznie 40% punktów zachodzi dodatkowy warunek . Dodatkowo, w testach wartych łącznie 10% punktów wszystkie ściany mają być oświetlone.

Wyjście

Dla każdego zestawu danych Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedno słowo: TAK - jeżeli da się ustawić lampę zgodnie z podanymi warunkami, lub NIE - w przeciwnym przypadku.

Przykład

Na rysunkach pod przykładami pogrubione boki oznaczają ściany, które mają być zaciemnione, a pozostałe boki - ściany, które mają być oświetlone. Rysunek do pierwszego przykładu przedstawia poprawne położenie lampy.

Dla danych wejściowych:

1
16
5 -3
4 -4
3 -7
0 -5
-3 -7
-4 -4
-5 -3
-1 -1
-4 3
-2 4
-1 2
0 7
1 2
2 4
4 3
1 -1
C
S
S
S
S
C
C
S
S
C
S
S
C
S
S
C

poprawną odpowiedzią jest:

TAK

natomiast dla danych wejściowych:

2
3
0 0
0 1
1 0
S
C
S
3
0 0
0 1
1 0
S
S
S

poprawnym wynikiem jest:

NIE
TAK

Autor zadania: Jakub Wojtaszczyk.