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.
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 x2 + y2 = r2. Oto przykładowa realizacja podanego algorytmu:
- def IlePunktow(r):
- ile = 0
- ceiled = int(math.ceil(r))
- for x in range(-ceiled, ceiled + 1):
- for y in range(-ceiled, ceiled + 1):
- if x*x + y*y <= r*r:
- ile += 1
- return ile
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(r2) (licząc dokładniej do przejrzenia jest prawie 4r2 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:
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:
- def IlePunktow(r):
- ile = 0
- ceiled = int(math.ceil(r))
- x = ceiled
- for y in range(1, ceiled + 1):
- while (x > 0 and x * x + y * y > r * r):
- x -= 1
- ile += x
- return (ile + int(r)) * 4 + 1
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.
- r = float(input("Promień okregu\n r = "))
- ile = IlePunktow(r)
- print("Punktów w środku:", ile)
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.