[SMWP_101] Wieżowce

0 Flares Twitter 0 Facebook 0 0 Flares ×

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_101/

Omówienie:
Zadanie polega na znalezieniu punktu, który ukazał się najwięcej razy na wejściu. Dodatkowo ten punkt musi należeć do koła o środku xc i yc oraz promieniu r. Szukany punkt możemy znaleźć na kilka sposobów. Jednym z nich jest stworzenie struktury do której będziemy zapisywać wszystkie punkty.Należy je posortować względem współrzędnych aby potem tylko poprzez 1 przejście pętli zaktualizować ilość wystąpień danego punktu oraz sprawdzić czy należy do podanego koła.
Innym sposobem jest skorzystanie z własności iż r<=100. Daje to nam możliwość stworzenia tablicy. Na początku należy sprawdzić czy dany punkt znajduje się w obrębie miasta,
następnie możemy go przesunąć o wektor[-xc,-yc] i zapisać w tablicy.
Pozostaje nam tylko przejść przez tablicę szukając najwyższej wartości.

Print Friendly

Dodaj komentarz

Wymagane pola są oznaczone *.