Prosty wielokąt (NWERC 2009)

Po NWERC 2009 żałowałem, że nie udało nam się wklepać jeszcze jednego zadania - "Prostego wielokąta", a miało to zadanko wiele drużyn. Treść zadania jest dostępna tutaj: http://www.nwerc.eu/results/nwerc09.pdf (strona 19).

Jak widać nawet historyjki nie chciało się wymyślać ;) A do rozwiązania wystarczył jeden prosty pomysł, którego nam zabrakło...

A pomysł jest taki: akceptowany jest każdy poprawny wielokąt, czyli trzeba go tylko narysować w jakiś prosty sposób ;) Najprostszy sposób jest chyba taki:

0. Traktujemy punkty jak liczby zespolone.
1. Wybieramy punkt na brzegu zbioru - najlepiej taki o najmniejszej części urojonej.
2. Przesuwamy środek układu współrzędnych w ten punkt.
3. Wielokąt rysujemy zaczynając od centrum układu współrzędnych i dołączamy do naszego wielokąta kolejne punkty w kolejności rosnącego argumentu (kąta w postaci trygonometrycznej) liczby zespolonej.

Ponieważ wszystkie nasze liczby są ponad osią liczb rzeczywistych (lub na niej) argument może mieć wartości tylko od 0 do π. Również ponieważ żadne 3 punkty nie są współliniowe - wartość ta nie może się powtarzać.

Funkcja arg w C++ może czasami zwrócić nam -π kiedy liczba leży na osi rzeczywistej, wystarczy wtedy dodać 2π do wyniku by mieć zawsze wartości dodatnie ;) Wtedy nasz pierwszy, wybrany punkt może dostać wartość (-1), aby zawsze pierwszy pojawił się w sortowaniu ;)

Mając ten pomysł można napisać kod taki jak poniżej:

http://pastebin.com/f6c5d51c1

Grrrr... ;)