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. static int IlePunktow(double r)
2. {
3. int ile = 0;
4. for (int x = -(int)Math.Ceiling(r); x <= r; x++)
5. {
6. for (int y = -(int)Math.Ceiling(r); y <= r; y++)
7. {
8. if (x * x + y * y <= r * r)
9. {
10. ile++;
11. }
12. }
13. }
14. return ile;
15. }

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. static int IlePunktow(double r)
2. {
3. int ile = 0;
4. int x = (int)Math.Ceiling(r);
5. for (int y = 1; y <= (int)Math.Ceiling(r); y++)
6. {
7. while (x > 0 && x * x + y * y > r * r)
8. {
9. x--;
10. }
11. ile += x;
12. }
13. return (ile + (int)r) * 4 + 1;
14. }

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. static void Main(string[] args)
2. {
3. Console.Write("Promień okregu\n r = ");
4. double r = double.Parse(Console.ReadLine());
5. int ile = IlePunktow(r);
6. Console.WriteLine("Punktów w środku: {0}", ile);
7. Console.ReadKey();
8. }

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