17205. Punkty w kole [AL_12_02]

Zadania:
http://pl.spoj.com/problems/AL_12_02
http://spoj.com/ALGOLIGA/problems/AL_12_02

Skrócony opis problemu:

Dla koła o danym $r \in \mathbb{N}$ oraz środku o współrzędnych całkowitych zliczyć ilość punktów o współrzędnych całkowitych leżących w lub na brzegu tego koła.

Jest to tzw. problem koła Gaussa (ang. Gauss circle problem).

Rozwiązanie naiwne:

Można skorzystać ze wzoru:

$$1+4 \sum_{i=1}^{r^2} (-1)^{i-1}\left\lfloor \frac{r^2}{2i-1} \right\rfloor$$

lub:

$$1+4 \sum_{i=0}^{\infty} \left( \left \lfloor \frac{r^2}{4i+1}\right \rfloor -\left \lfloor \frac{r^2}{4i+3} \right \rfloor \right)$$

Źródło: http://mathworld.wolfram.com/GausssCircleProblem.html

Złożoność: $O(r^2)$. Dla pierwszego wzoru jest to jasne, a dla drugiego osiągniemy taki efekt dla warunku końcowego $r^2 > 4i+1$. Floor dla takich danych jest bowiem równy 0, więc wynik się nie zmieni.

Rozwiązanie sprytne:

Można skorzystać z tego wzoru:

$$1 + 4\left\lfloor r \right\rfloor + 4\sum_{i=1}^{\left\lfloor r \right\rfloor} \left\lfloor\sqrt{r^2-i^2}\right\rfloor$$

Złożoność: $O(r)$.

Wyprowadzenie wzoru:

Autorem dowodu jest Adam Bąk.

Wzór ów działa również dla $r$ rzeczywistego, więc uogólnimy, że $r \in \mathbb{R}$. Bez straty ogólności załóżmy też, że środek koła jest w punkcie $\left(0;0\right)$. Chcemy zatem znaleźć moc (liczność) zbioru $\left\lbrace \left(x;y\right) \in \mathbb{Z}^2 : x^2+y^2 \le r^2\right\rbrace$ (gdyż $x^2+y^2 \le r^2$ to definicja koła).

Zliczmy najpierw wszystkie punkty na osiach układu współrzędnych. Rozpatrzmy sobie najpierw oś OX dla $x \in \mathbb{N}_{+}$. Liczb tych będzie $\left\lfloor r \right\rfloor$. Np. dla $r=4.5$ będą to punkty: $\left(1;0\right)$, $\left(2;0\right)$, $\left(3;0\right)$, $\left(4;0\right)$ (punkt $\left(5;0\right)$ jest już poza obszarem koła). Będzie tak również dla osi OX dla ujemnych $x$ oraz dla 2 odpowiadających części osi OY. Będzie zatem $4\left\lfloor r \right\rfloor + 1$ punktów na osiach. Czemu $+1$? Bo dodajemy także środek koła, który jest wspólny dla wszystkich fragmentów osi, a możemy policzyć do tylko raz.

Pozostałe punkty również możemy sobie podzielić na 4 ćwiartki, a potem przemnożyć otrzymany wynik przez 4 (jako że są one symetryczne i zawierają tyle samo punktów, o które nam chodzi). Musimy więc obliczyć $\left| \left\lbrace \left(x;y\right) \in \mathbb{N}_{+}^2 : x^2+y^2 \le r^2\right\rbrace \right|$. Podzielmy sobie problem na znalezienie wszystkich punktów, ale dla konkretnego $x \in \mathbb{N}_{+}$, a następnie zsumujmy wyniki dla wszystkich możliwych $x$ (a będzie ich $\left\lfloor r \right\rfloor$). A zatem, dla danego $x$ ilość punktów o współrzędnych całkowitych, leżących wewnątrz koła jest równa największemu $y$, które mieści się w kole dla tego $x$. Owo $y$ wynosi $\left\lfloor \sqrt{r^2-x^2} \right\rfloor$, a bierze się to z przekształcenia definicji koła na $\ y^2 \le r^2-x^2$. Otrzymujemy więc $4 \sum\limits_{i=1}^{\left\lfloor r \right\rfloor} \left\lfloor\sqrt{r^2-i^2}\right\rfloor$ dla pozostałych punktów.

A więc weźmy sobie np. $r=3$. Punktów na osiach będzie $1 + 4 \cdot 3 = 13$. Teraz bierzemy sobie $x=1$. Ile będzie $y$ dla tego $x$? Ano $\left\lfloor\sqrt{3^2-1^2}\right\rfloor = 2$. Dla $x=2$ dostaniemy $\left\lfloor\sqrt{3^2-2^2}\right\rfloor = 2$, a dla $x=3$ otrzymamy $\sqrt{3^2-3^2} = 0$. Ostateczny wynik to zatem $13+4 \cdot \left(2+2+0\right) = 29$.