In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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:
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.
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.
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.