629. Skąpiec [MISER]

Zadanie:
https://pl.spoj.com/problems/MISER

Skrócony opis problemu:

Dla danego zbioru $n$ punktów w przestrzeni 2-wymiarowej należy wyznaczyć dowolne 2 punkty, takie że okrąg utworzony na nich oraz na pierwszym punkcie z wejścia (nazwijmy go $A$) nie zawiera w sobie żadnego innego punktu (mogą jednak się znaleźć punkty na samym okręgu). Żadne 3 punkty nie są współliniowe.

1078. Kreskowany rysunek [ETI07E2]

Zadanie:
https://pl.spoj.com/problems/ETI07E2

Skrócony opis problemu:

Dla wielokąta wyznaczonego przez ciąg n znaków [NSWE] oznaczających odpowiednio kierunki: północ, południe, zachód, wschód wyznaczyć ilość linii potrzebnych do jego zakreskowania liniami prostymi pod kątem $45\circ$. Wszystkie boki tego wielokąta są albo równoległe, albo prostopadłe do osi OX.

628. Półki [SHELVES]

Zadanie:
https://pl.spoj.com/problems/SHELVES

Skrócony opis problemu:

Mając półki ustawione ukośnie w $n$ ($n \le 1000$) kolumnach oraz $k$ ($k \le 250000$) piłek, które są kolejno spuszczane w różnych kolumnach z górnych półek określ gdzie spadnie ostatnia piłka, jeśli po każdym stoczeniu się piłki po półce odwraca się jej ustawienie (jeśli nie jest ona półką skrajną). A więc półki \ zamieniają się na / i odwrotnie.

Przykładowo, jeśli mamy jedną piłkę i taki zestaw półek:

o    
\ \ /
 / / 
\ \ /

To po sturlaniu się piłki po wszystkich 3 półkach, ich rozkład będzie wyglądał następująco:

\ \ /
 \ / 
\ \ /
o  

Jak widać, półki po bokach nie zmieniają nachylenia, gdyż wtedy piłka wypadłaby poza planszę. Zmianie uległa więc tylko nachylenie czerwonej półki.

W zadaniu półki \ są podane jako 1, a / jako -1.