Całkowite punkty w okregu

0

Witam. Chciałbym uzyskać jakieś wskazówki dotyczące programu do którego nie wiem jak się zabrać.
Treść:
Podaj ilość punktów całkowitych należących do okręgu o promieniu r . Środek okręgu to (0,0). Promień wpisywany z klawiatury.

Po przemyśleniach i wyrysowaniu sobie tego graficznie na papierze wpadłem na pomysł ( o ile wgl jest dobry) ze po wprowadzeniu promienia, można ten duży okrąg podzielić na małe i zaliczać ich punkty. A do zaliczania punktów użyłbym 2 pętli jedna do x a druga w niej do y. Sęk w tym ze nie mam pomysłu jak to napisać i chciałbym uzyskać jakieś wskazówki.

P.s jestem początkujący, ale dużo rzeczy rozumiem.

0

A skąd te punkty?

0

jeśli środek to 0,0 i masz promień r to przelatujesz po forze(X) w forze(y) współrzędne X i Y w zakresie -r/2; r/2 i mając w tej sposób współrzędne sprawdzasz czy odległosć danego punktu od punktu 0,0 jest mneijsza lub równa r.

0

Może stary artykuł Krashana się Tobie przyda :) Jest tam troszkę inne podejście do tematu: http://teleinfo.pb.edu.pl/krashan/articles/elipsy/

2

Domyślam się że chodzi o koło a nie okrąg. Więc:

Rozwiązanie O(n^2):

result = 0;
for x in [-r; r]:
    for y in [-r; r]:
        if inside_circle(x, y):
           result++
return result;

Gdzie inside_circle to funkcja sprawdzająca czy dany punkt leży w szukanym kole (to trywialne i wynika bezpośrednio z równania koła).

Rozwiązanie O(n):

result = 0
for x in [-r; r]:
    result += vertical_points(x) * 2 - 1
return result

Gdzie vertical_points(x) to funkcja mówiąca jak wiele całkowitych punktów znajduje się w kole dla danej współrzędnej x, powyżej osi OX:

443fd308d2.png
(zaawansowana ilustracja przykładowa, tutaj vertical_points(1) = 6, vertical_points(2) = 5, vertical_points(3) = 5, vertical_points(4) = 4, vertical_points(5) = 2).

Jak tą funkcję zdefiniować (bez pętli)?

x^2+y^2<=r^2
y^2<=r^2-x^2    // tylko y >= 0
y <= sqrt(r^2-x^2)

(przy czym wynikiem jest floor(y), bo bierzemy pod uwagę tylko punkty całkowite).

PS. Wszystkie przykłady dla kół o środku w (0, 0), ale bardzo prosto to uogólnić do dowolnie położonych kół.

PPS. Obie funkcje można przyśpieszyć o stałą, zauważając że wystarczy wyliczyć ilośc punktów w ćwiartce/połowie koła, i pomnożyć razy cztery/dwa. Ale komplikowało to rozwiązanie (trzeba pilnować żeby dwa razy nie policzyć jednego punktu) więc nie zostało tu zaimplementowane.

PPPS. Czy da się to zrobić w czasie lepszym niż O(n) - nie wykluczam, ale nie mam pomysłu z głowy od razu.
Może np. jakiś matematyk potrafiłby znaleźć na to bezpośredni wzór, bez żadnych petli.

1 użytkowników online, w tym zalogowanych: 0, gości: 1