Punkty w Kole

Zadanie

Znajdź wszystkie punkty o całkowitych współrzędnych, które znajdują się wewnątrz koła znajdującego się w punkcie (0, 0) i o pewnym promieniu r. Algorytm powinien zwrócić ile takich punktów jest.

Przykład

Poniżej zostały przedstawione przykładowe koła o podanych promieniach r oraz zaznaczone punkty na siatce o całkowitych współrzędnych, które się mieszczą w kole.

r = 1, 5 punktów

r = sqrt(2) = 1.414.., 9 punktów

r = 2, 13 punktów

Implementacja

Naiwne Poszukiwanie

Pierwszy sposób wyszukiwania punktów polega na przejrzeniu wszystkich punktów znajdujących się wewnątrz kwadratu opisanego na kole. Dla każdego punktu następnie jest sprawdzany warunek x² + y² = r². Oto przykładowa realizacja podanego algorytmu:

1. int IlePunktow(double r) {
2.   int ile = 0;
3.   for (int x = -ceil(r); x <= r; x++) {
4.     for (int y = -ceil(r); y <= r; y++) {
5.       if (x * x + y * y <= r * r) {
6.         ile++;
7.       }
8.     }
9.   }
10.   return ile;
11. }

Cały algorytm składa się z licznika i dwóch pętli. Nie jest to metoda optymalna, ponieważ złożoność rośnie kwadratowo tj. O(r²) (licząc dokładniej do przejrzenia jest prawie 4r² punktów).

Optymalny

Zauważmy, że koło składa się z czterech identycznych ćwiartek, a ponadto pewne jest, że punkt środkowy zawsze istnieje (z założenia koło ma r > 0). Wzdłuż dowolnej osi od środka na zewnątrz jest floor(r) punktów. Pozostaje zatem dodać do tej wartości ilość punktów w ćwiartce, ale nie na krawędzi, a następnie pomnożyć przez 4 i dodać jeden punkt. Przyjrzyjmy się poniższej grafice:

Przykład podziału

W celu policzenia ile jest "zielonych" punktów to wykonujemy następujące operacje: ustawiamy x na ilość punktów wzdłuż osi oraz y = 1. Następnie jeśli punkt znajduje się poza kołem to zmniejszamy x tak długo, aż znajdziemy się w kole. Wartość x zmniejszamy, aż do osiągnięcia wartości 0. Proces ten powtarzamy dla każdego y, który jest ograniczony promieniem koła r.

Oto przykładowy kod realizujący to zadanie:

1. int IlePunktow(double r) {
2.   int ile = 0;
3.   int x = ceil(r);
4.   for (int y = 1; y <= ceil(r); y++) {
5.     while (x > 0 && x * x + y * y > r * r) {
6.       x--;
7.     }
8.     ile += x;
9.   }
10.   return (ile + int(r)) * 4 + 1;
11. }

Zaletą takiego rozwiązania jest znaczne poprawienie złożoności, ponieważ warunek zostanie policzony dla maksymalnie r punktów. Ponadto znaczna część punktów jest policzona bez sprawdzania warunku na bycie wewnątrz koła.

Testowanie funkcji

Oto przykładowy fragment kodu do wczytania promienia koła, a następnie wypisaniu ile punktów znajduje się w środku.

1. int main () {
2.   double r;
3.   cout << "Promien okregu\n r = ";
4.   cin >> r;
5.   int ile = IlePunktow(r);
6.   cout << "Punktow w srodku " << ile;
7.   system("pause");
8.   return 0;
9. }

Uwaga: przedstawione w zadaniu metody wymagają podania promienia r z odpowiednią dokładnością. W przypadku sqrt(2) należy podać wartość 1.415, ponieważ 1.414 nie pokaże prawidłowego wyniku.

• Kod źródłowy Naiwne Poszukiwanie
• Kod źródłowy Optymalny