h2(#problema1). Problema 1
bq. Să se determine numărul de puncte de coordonate întregi prin care trece segmentul determinat de punctele $(0, 0)$ şi $(M, N)$. De exemplu, pentru $M=9$ şi $N=12$ pe segment vor fi $4$ puncte de coordonate întregi.
bq. Să se determine numărul de puncte de coordonate întregi prin care trece segmentul determinat de punctele $(0, 0)$ şi $(N, M)$. De exemplu, pentru $N = 9$ şi $M = 12$ pe segment vor fi $4$ puncte de coordonate întregi.
!probleme-cu-puncte-laticiale?img1.JPG!
p=. !probleme-cu-puncte-laticiale?img1.JPG!
h3. Rezolvare
Putem considera doar cazurile în care $0 ≤ N ≤ M$, dacă $N = 0$ atunci evident avem $M+1$ puncte pe segment. Astfel trebuie să rezolvăm doar cazul în care $1 ≤ N ≤ M$.
Evident că orice punct $(x, y)$, pentru a fi pe segmentul nostru, trebuie să satisfacă ecuaţia $y=M/N*x$. Această ecuaţie are ca soluţie un număr natural doar dacă $M*x$ se divide cu $N$, de aici dacă $D=cmmdc(N, M)$ atunci $x$ se divide cu $N/D$, deci $x$ de forma $k*N/D => y=k*M/D$. Pentru ca punctul $(x, y)$ să aparţină segmentului, trebuie ca $0 ≤ x ≤ N$ şi $0 ≤ y ≤ M$ astfel $0 ≤ k ≤ D$. Deci numărul de puncte de pe un segment de la $(0, 0)$ la $(N, M)$ este egal cu cel mai mare divizor comun al numerelor $M$ şi $N$ la care adăugăm $1$. Putem determina acest număr în complexitate $O(log (N + M))$.
Putem considera doar cazurile în care $0 ≤ N ≤ M$. Dacă $N = 0$ atunci, evident, avem $M + 1$ puncte pe segment. Astfel, trebuie să rezolvăm doar cazul în care $1 ≤ N ≤ M$.
Evident că orice punct $(x, y)$, pentru a fi pe segmentul nostru, trebuie să satisfacă ecuaţia $y = (M / N) * x$. Această ecuaţie are ca soluţie un număr natural doar dacă $M * x$ se divide cu $N$. De aici, dacă $D = cmmdc(M, N)$ atunci $x$ se divide cu $N / D$. Obţinem, astfel, $x$ de forma $k * (N / D)$, de unde rezultă că $y$ este de forma $y = k * (M / D)$. Pentru ca punctul $(x, y)$ să aparţină segmentului, trebuie ca $0 ≤ x ≤ N$ şi $0 ≤ y ≤ M$, şi, înlocuind în a doua inegalitate pe $y$ avem $0 ≤ k ≤ D$. În concluzie, numărul de puncte de pe un segment de la $(0, 0)$ la $(N, M)$ este egal cu cel mai mare divizor comun al numerelor $M$ şi $N$ la care adăugăm $1$. Putem determina acest număr în complexitate $O(log (N + M))$.
h2(#problema2). Problema 2
bq. Se dă un triunghi cu vârfurile de coordonate întregi. Se cere să se determine numărul de puncte de coordonate întregi ce se află în interiorul triunghiului sau pe laturile lui. De exemplu un triunghi cu vârfurile de coordonate $(1, 5)$, $(5, 1)$ şi $(6, 6)$ are $16$ puncte în interior.
bq. Se dă un triunghi cu vârfurile de coordonate întregi. Se cere să se determine numărul de puncte de coordonate întregi ce se află în interiorul triunghiului sau pe laturile lui. De exemplu, un triunghi cu vârfurile de coordonate $(1, 5)$, $(5, 1)$ şi $(6, 6)$ are $16$ puncte în interior.
!probleme-cu-puncte-laticiale?img2.JPG!
p=. !probleme-cu-puncte-laticiale?img2.JPG!
h3. Rezolvare
Pentru un dreptunghi cu laturile paralele cu axele de coordonate de lungime $M$ şi lăţime $N$ avem că numărul de puncte situate strict în interiorul dreptunghiului este $(M–1)×(N–1)$, iar numărul de puncte situate pe laturile poligonului este $2M + 2N$. Dacă notăm cu $B$ numărul de puncte de pe laturi, cu $I$ numărul de puncte situate strict în interiorul unui dreptunghi şi cu $A$ aria dreptunghiului, observăm că $I+B/2–1 = (M–1)×(N–1)+M+N–1 = M×N = A$.
În cazul triunghiurilor dreptunghice ce au două catete vom vedea că această formulă se păstrează. Evident avem că $A = (M×N)/2$. Pe ipotenuza triunghiului vom avea $D$ puncte $(D = cmmdc(M, N)+1$, dar aceasta nu ne interesează pe moment), deci numărul de puncte de pe laturile triunghiului este $B = M+N+D–1$. Numărul de puncte $I$ din interiorul triunghiului este numărul de puncte din interiorul dreptunghiului $(M-1)×(N-1)$ din care se scad punctele interioare de pe diagonala $D–2$, rezultatul împărţindu-se apoi la $2$, de aici avem $I = ((M-1)×(N-1)–D+2)/2$.
Verificăm formula $I+B/2–1 = (M-1)×(N-1)/2–D/2+1+M/2+N/2+D/2+1/2 = (M×N)/2$.
Deci formula se verifică şi pe astfel de triunghiuri.
Acum ne uităm la cel mai mic dreptunghi ce conţine un triunghi oarecare, acest dreptunghi poate fi împărţit în patru triunghiuri din care unul este cel iniţial, iar celelalte sunt trei triunghiuri dreptunghice pentru care catetele merg de-a lungul liniilor laticiale. Vom vedea că formula noastră se verifică şi pentru triunghiuri oarecare. Notăm cu $I{~d~}$ numărul de puncte înterioare dreptunghiului, $A{~d~}$ aria dreptunghiului şi $B{~d~}$ numărul de puncte de pe laturile dreptunghiului, cu $I{~1~}$, $I{~2~}$, $I{~3~}$ numărul de puncte din interiorul celor trei triunghiuri dreptunghice, $B{~1~}$, $B{~2~}$, $B{~3~}$ numărul de puncte de pe laturile celor trei triunghiuri, iar $A{~1~}$, $A{~2~}$ şi $A{~3~}$ ariile celor trei triunghiuri. Avem că $I = I{~d~}–I{~1~}–I{~2~}–I{~3~}–B+3$ (trebuie să eliminăm punctele de pe laturile triunghiului interior şi să avem grijă de vârfurile acestui triunghi), $B = B{~1~}+B{~2~}+B{~3~}–B{~d~}$ iar $A = A{~d~}–A{~1~}–A{~2~}–A{~3~}$. De aici avem că $I+B/2–1 = I{~d~}–I{~1~}–I{~2~}–I{~3~} - B{~1~}/2-B{~2~}/2-B{~3~}/2+B{~d~}/2–1+3 = (I{~d~}+B{~d~}/2–1)–(I{~1~}+B{~1~}/2–1) - (I{~1~}+B{~1~}/2–1)-(I{~1~}+B{~1~}/2–1) = A{~d~}–A{~1~}–A{~2~}–A{~3~} = A$, deci egalitarea este valabilă şi pentru triunghiuri oarecare.
Pentru un dreptunghi cu laturile paralele cu axele de coordonate de lungime $M$ şi lăţime $N$ avem că numărul de puncte situate strict în interiorul dreptunghiului este $(M – 1)*(N – 1)$, iar numărul de puncte situate pe laturile poligonului este $2M + 2N$. Dacă notăm cu $B$ numărul de puncte de pe laturi, cu $I$ numărul de puncte situate strict în interiorul unui dreptunghi şi cu $A$ aria dreptunghiului, observăm că $I + B/2 – 1 = (M – 1) * (N – 1) + M + N – 1 = M * N = A$.
În cazul triunghiurilor dreptunghice ce au două catete vom vedea că această formulă se păstrează. Evident avem că $A = (M * N)/2$. Pe ipotenuza triunghiului vom avea $D$ puncte ($D = cmmdc(M, N) + 1$, dar aceasta nu ne interesează pe moment). Rezultă că numărul de puncte de pe laturile triunghiului este $B = M + N + D – 1$. Numărul de puncte $I$ din interiorul triunghiului este numărul de puncte din interiorul dreptunghiului $(M - 1) * (N - 1)$ din care se scad punctele interioare de pe diagonala $D – 2$, rezultatul împărţindu-se apoi la $2$. De aici avem $I = ((M - 1) * (N - 1) – D + 2) / 2$.
!probleme-cu-puncte-laticiale?img3.JPG!
Verificăm formula $I + B/2 – 1 = (M - 1) * (N - 1)/2 – D/2 + 1 + M/2 + N/2 + D/2 + 1/2 = (M * N)/2$. Deci formula se verifică şi pe astfel de triunghiuri.
Acum ne uităm la cel mai mic dreptunghi ce conţine un triunghi oarecare. Acest dreptunghi poate fi împărţit în patru triunghiuri din care unul este cel iniţial, iar celelalte sunt trei triunghiuri dreptunghice pentru care catetele merg de-a lungul liniilor laticiale. Vom vedea că formula noastră se verifică şi pentru triunghiuri oarecare. Notăm cu $I{~d~}$ numărul de puncte interioare dreptunghiului, $A{~d~}$ aria dreptunghiului şi $B{~d~}$ numărul de puncte de pe laturile dreptunghiului, cu $I{~1~}$, $I{~2~}$, $I{~3~}$ numărul de puncte din interiorul celor trei triunghiuri dreptunghice, $B{~1~}$, $B{~2~}$, $B{~3~}$ numărul de puncte de pe laturile celor trei triunghiuri, iar $A{~1~}$, $A{~2~}$ şi $A{~3~}$ ariile celor trei triunghiuri. Avem că $I = I{~d~}–I{~1~}–I{~2~}–I{~3~}–B+3$ (trebuie să eliminăm punctele de pe laturile triunghiului interior şi să avem grijă de vârfurile acestui triunghi), $B = B{~1~}+B{~2~}+B{~3~}–B{~d~}$ iar $A = A{~d~}–A{~1~}–A{~2~}–A{~3~}$. De aici avem că $I+B/2–1 = I{~d~}–I{~1~}–I{~2~}–I{~3~} - B{~1~}/2-B{~2~}/2-B{~3~}/2+B{~d~}/2–1+3 = (I{~d~}+B{~d~}/2–1)–(I{~1~}+B{~1~}/2–1) - (I{~1~}+B{~1~}/2–1)-(I{~1~}+B{~1~}/2–1) = A{~d~}–A{~1~}–A{~2~}–A{~3~} = A$, deci egalitarea este valabilă şi pentru triunghiuri oarecare.
p=. !probleme-cu-puncte-laticiale?img3.JPG!
Acum aria triunghiului cu vârfurile $(x1, y1)$, $(x2, y2)$, $(x3, y3)$ o putem afla uşor folosind formula lui Heron sau folosind
<tex> \frac {1} {2} \cdot | \left| \begin{array}{ccc}
