Zbiór zadań, (zadania różne)
Zadanie 315
Ile punktów kratowych (punktów o całkowitych współrzędnych) zawiera koło o środku w początku układu współrzędnych i promieniu $100$?
Rozwiązanie
W zadaniu szukamy liczbę par punktów $(x,y)\in Z$ takich, że $x^2+y^2\le r^2$.
Nasze poszukiwania możemy ograniczyć do jednej ćwiartki i wynik pomnożyć przez $4$.
Dla każdego $0 \le x < r$ należy policzyć liczbę różnych $y \ge 1$ takich, że $x^2+y^2\le r^2$. Jest ich $\left \lfloor \sqrt{r^2-x^2}\right\rfloor$, co wynika z przekształcenia nierówności koła. Należy zauważyć, że pozostaje jeszcze punkt $(0,0)$, który po zsumowaniu czterech ćwiartek będzie dopełnieniem wszystkich punktów w kole.
Rozwiązaniem jest więc $1 + 4\sum_{x=0}^{r-1}\left\lfloor\sqrt{r^2-x^2}\right\rfloor$.
Dla $r=100$ otrzymujemy $1 + 4\sum_{x=0}^{99}\left\lfloor\sqrt{100^2-x^2}\right\rfloor = 31417$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>