5. Potyczki Informatyczne Nowej Generacji

Zadanie eliminacyjne w konkursie WIPING5 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Kodekoder

Na kartce w kratkę zaznaczono pewne punkty i połączono je odcinkami w ten sposób, że każdy punkt wchodzi w skład co najmniej jednego odcinka. Twoje zadanie polega na sprawdzeniu, czy uzyskaną figurę można było narysować za jednym zamachem bez odrywania pisaka od kartki, nie przechodząc przez żaden z odcinków więcej niż raz.

Wejś›cie

• kolejno:
  • wiersz tekstu zawierający liczbę testów n
  • liczba odcinków w teście t
  • t wierszy opisujących odcinki, każdy zawierający cztery (rozdzielone spacjami) liczby całkowite określające odpowiednio współrzędne początku i końca odcinka

Wyjś›cie

• dla każdego testu wyprowadź w osobnej linii słowo TAK, jeśli tę figurę da się narysować bez odrywania pisaka od kartki, bądź słowo NIE w przeciwnym wypadku.

Przykł‚ad

Wejś›cie: 

2

5

-1 1 1 1

1 1 -1 -1

-1 -1 -1 1

-1 1 1 -1

1 -1 1 1

6

0 0 0 1

1 0 1 1

0 2 1 2

0 2 0 1

1 2 1 1

1 1 0 1

Wyjście:

TAK

NIE

Informacje dodatkowe

• program zostanie uruchomiony 10 razy dla różnych zestawów danych

• każde poprawne rozwią…zanie daje 10% punktacji zadania

• zadanie ma wartość‡ punktową… 5,0