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.
Bajtazar przygotowuje najtrudniejsze zadanie na ostatnią, zdalną rundę Potyczek Algorytmicznych 2012. Fakt, że problem dotyczy geometrii obliczeniowej, a konkretnie przecinania wielokąta z okręgami, zupełnie nikogo nie zaskakuje.
Jak wiadomo, największą trudnością w geometrii obliczeniowej jest radzenie sobie z rozmaitymi przypadkami szczególnymi. Bajtazar ustalił, że w przygotowywanym przez niego zadaniu najtrudniej jest uporać się z sytuacją, gdy dany wielokąt ma pole równe liczbie jego wierzchołków. Ponadto, taki wielokąt powinien mieć boki równoległe do osi prostokątnego układu współrzędnych i każde dwa kolejne boki wielokąta powinny być prostopadłe. Boki wielokąta nie mogą mieć punktów wspólnych, oprócz wierzchołków wspólnych dla dwóch kolejnych boków wielokąta.
Generowanie takich wielokątów przerosło możliwości Bajtazara, dlatego poprosił Cię o pomoc.
W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę wierzchołków szukanego wielokąta.
Jeśli nie da się skonstruować -wierzchołkowego wielokąta spełniającego warunki zadania, należy wypisać słowo NIE . W przeciwnym przypadku na wyjściu należy wypisać dokładnie wierszy. W -tym wierszu powinny znaleźć się dwie liczby całkowite i , oznaczające współrzędne -tego wierzchołka szukanego wielokąta. Wierzchołki powinny być wypisane zgodnie z kolejnością ich występowania na obwodzie wielokąta (kierunek wypisywania wierzchołków wzdłuż obwodu może być dowolny). Wartość bezwzględna liczb wypisanych na wyjściu nie powinna przekraczać .
Dla danych wejściowych:
4
poprawną odpowiedzią jest:
0 0 2 0 2 2 0 2
Autor zadania: Jakub Łącki.