Diferente pentru probleme-cu-puncte-laticiale intre reviziile #13 si #23

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Probleme cu puncte laticiale
== include(page="template/implica-te/scrie-articole" user_id="portocala") ==
 
(Categoria _Matematică_, Autor _Cosmin Negruşeri_)
(toc){width: 25em}*{text-align:center;} *Conţinut*
h2(#introducere). Introducere
Articolul de faţă se va concentra pe probleme în care vor apărea puncte de coordonate întregi care sunt numite puncte laticiale. Sursele [1] şi [2] menţionate în 'bibliografie':probleme-cu-puncte-laticiale#bibliografie conţin câte un capitol despre puncte laticiale care, deşi sunt mai matematice decât acest articol, pot fi interesante pentru un elev în pregătirea pentru olimpiadă. Să vedem acum câteva probleme ce au apărut pe la concursurile de programare.
Articolul de faţă se va concentra pe probleme în care vor apărea puncte de coordonate întregi care sunt numite puncte laticiale. Sursele [1] şi [2] menţionate în 'bibliografie':probleme-cu-puncte-laticiale#bibliografie conţin câte un capitol despre puncte laticiale care, deşi sunt mai riguros tratate decât în acest articol, pot fi interesante pentru un elev în pregătirea pentru olimpiadă. Să vedem acum câteva probleme ce au apărut pe la concursurile de programare.
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 $(N, M)$. De exemplu, pentru $N = 9$ şi $M = 12$ pe segment vor fi $4$ puncte de coordonate întregi.
p=. !probleme-cu-puncte-laticiale?img1.JPG!
p=. !probleme-cu-puncte-laticiale?img1.JPG 70%!
h3. Rezolvare
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 în puncte laticiale. 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.
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). 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$.
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$.
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.
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/21 = I{~d~}I{~1~}I{~2~}I{~3~} - B{~1~}/2-B{~2~}/2-B{~3~}/2+B{~d~}/21+3 = (I{~d~}+B{~d~}/21)(I{~1~}+B{~1~}/21) - (I{~1~}+B{~1~}/21)-(I{~1~}+B{~1~}/21) = A{~d~}A{~1~}A{~2~}A{~3~} = A$, deci egalitarea este valabilă şi pentru triunghiuri oarecare.
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}
x1 & y1 & 1 \\
x2 & y2 & 1 \\
x3 & y3 & 1 \end{array} \right| |.  </tex>
Acum aria triunghiului cu vârfurile $(x1, y1)$, $(x2, y2)$, $(x3, y3)$ o putem afla uşor folosind 'formula lui Heron':http://en.wikipedia.org/wiki/Heron%27s_formula sau folosind determinantul:
<tex> \displaystyle \frac {1} {2} \cdot | \left| \begin{array}{ccc}
x_{1} & y_{1} & 1 \\
x_{2} & y_{2} & 1 \\
x_{3} & y_{3} & 1 \end{array} \right| |.  </tex>
Numărul de puncte de pe laturile triunghiului poate fi determinat uşor folosind formula demonstrată în problema anterioară. Acum folosind formula $I+B/21 = A$ putem afla numărul $I$ şi problema e rezolvată prin întoarcerea numărului $I+B$. Complexitatea rezolvării este $O(log N)$ unde $N$ este valoarea maximă a coordonatelor.
Numărul de puncte de pe laturile triunghiului poate fi determinat uşor folosind formula demonstrată în problema anterioară. Acum, folosind formula $I + B/2 - 1 = A$ putem afla numărul $I$ şi problema e rezolvată prin întoarcerea numărului $I + B$. Complexitatea rezolvării este $O(log N)$ unde $N$ este valoarea maximă a coordonatelor.
h2(#problema3). Problema 3: 'Copaci':problema/copaci (info{_arena_})
bq. Macarie, după ce a muncit o viaţă întreagă, se decide la bătrâneţe să se retragă pe o insulă pentru a-şi găsi liniştea interioară şi a se dedica naturii. Astfel el cumpără o insula pe care cultivă pomi fructiferi. Insula poate fi reprezentată ca un poligon (nu neaparat convex) într-un sistem de axe de coordonate pozitive. Pomii sunt plantaţi doar la coordonate naturale.
Macarie este interesat de numărul de copaci pe care îl poate planta strict in interiorul insulei. În acest scop el va furnizează copacii care determina insula (vârfurile poligonului).
De exemplu pentru poligonul dat prin vârfurile $(0, 4)$, $(0, 5)$, $(2, 7)$, $(2, 4)$, $(6, 6)$ şi $(4, 0)$ avem $12$ puncte de coordinate întregi situate strict în interiorul poligonului.
bq. Se dă un poligon prin vârfurile sale aflate doar la coordonate numere naturale. Poligonul nu este neapărat convex. Se cere să se găsească numărul punctelor aflate strict în interiorul poligonului la coordonate numere întregi.
De exemplu, pentru poligonul dat prin vârfurile $(0, 4)$, $(0, 5)$, $(2, 7)$, $(2, 4)$, $(6, 6)$ şi $(4, 0)$ avem $12$ astfel de puncte.
!probleme-cu-puncte-laticiale?img4.JPG!
p=. !probleme-cu-puncte-laticiale?img4.JPG 80%!
h3. Rezolvare
Formula $I+B/2–1 = A$ prezentată mai sus se numeşte 'Teorema lui Pick':http://en.wikipedia.org/wiki/Pick%27s_theorem, iar ea este valabilă şi pentru poligoane oarecare. Acest fapt este adevărat pentru că orice poligon are o diagonală înterioară, această diagonală îl împarte în două poligoane distincte, dacă notăm $I{~1~}$ şi $I{~2~}$ punctele interioare celor două poligoane, $B{~1~}$ şi $B{~2~}$ punctele de pe laturile celor două poligoane, $A{~1~}$ şi $A{~2~}$ laturile celor două poligoane şi $D$ numărul de puncte de cooronate întregi de pe diagonală atunci dacă egalitatea ar fi fost satisfăcută pentru cele două poligoane atunci avem că $B{~1~}+B{~2~} = B+2D-2$, $I = I{~1~}+I{~2~}+D–2$. De aici avem $A = A{~1~}+A{~2~} = I{~1~}+B{~1~}/2–1+I{~2~}+B{~2~}/2-1 = I{~1~}+I{~2~}+B/2+D–1–2 = I+B/2–1$. Astfel putem demonstra prin inducţie că relaţia este satisfăcută pentru orice poligon.
Aria unui poligon poate fi calculată uşor folosind următoarea formulă
<tex> A = \sum (x_i \cdot y_{i+1}-x_{i+1} \cdot y_i) </tex>, unde punctul de indice $n+1$ este primul punct. Astfel obţinem un algoritm de complexitate $O(N log (MaxX + MaxY))$.
Formula $I + B/2 - 1 = A$ prezentată mai sus se numeşte 'Teorema lui Pick':http://en.wikipedia.org/wiki/Pick%27s_theorem, iar ea este valabilă şi pentru poligoane oarecare. Acest fapt este adevărat pentru că orice poligon are o diagonală interioară care îl împarte în două poligoane distincte. Dacă notăm $I{~1~}$ şi $I{~2~}$ punctele interioare celor două poligoane, $B{~1~}$ şi $B{~2~}$ punctele de pe laturile celor două poligoane, $A{~1~}$ şi $A{~2~}$ ariile celor două poligoane şi $D$ numărul de puncte de coordonate întregi de pe diagonală, atunci, dacă egalitatea ar fi fost satisfăcută pentru cele două poligoane, am avea că $B{~1~} + B{~2~} = B + 2D - 2$, $I = I{~1~} + I{~2~} + D - 2$. De aici avem $A = A{~1~} + A{~2~} = I{~1~} + B{~1~}/2 - 1 + I{~2~} + B{~2~}/2 - 1 = I{~1~} + I{~2~} + B/2 + D - 1 - 2 = I + B/2 - 1$. Astfel putem demonstra prin inducţie că relaţia este satisfăcută pentru orice poligon.
h2(#problema4). Problema 4 (Marele Premiu Paco 2000)
Aria unui poligon poate fi calculată uşor folosind următoarea formulă:
<tex> \displaystyle A = \sum_{i=1}^{n} (x_i \cdot y_{i+1}-x_{i+1} \cdot y_i) </tex>, unde punctul de indice $n + 1$ este primul punct. Astfel, obţinem un algoritm de complexitate $O(N log (Max_X + Max_Y))$.
Se dă o grilă de puncte laticeale de dimensiuni $N × N$, se cere să se determine numărul de pătrate care se pot forma astfel ca vârfurile lor să aparţină punctelor din grilă.
De exemplu pe o grilă de dimensiuni $3 × 3$ există $6$ pătrate.
h2(#problema4). Problema 4 (Marele Premiu Paco, 2000)
!probleme-cu-puncte-laticiale?img5.JPG!
bq. Se dă o grilă de puncte laticiale de dimensiuni $N × N$. Se cere să se determine numărul de pătrate care se pot forma astfel încât vârfurile lor să aparţină punctelor din grilă. De exemplu, pe o grilă de dimensiuni $3 × 3$ există $6$ pătrate.
h3. Rezolvare:
p=. !probleme-cu-puncte-laticiale?img5.JPG!
Un pătrat cu latură ce conţine $L$ puncte, ce are laturile paralele cu axele de coordonate poate fi translatat în $(N–L+1)×(N–L+1)$ poziţii diferite pe grila noastră.
h3. Rezolvare:
!probleme-cu-puncte-laticiale?img6.JPG!
Un pătrat cu $L$ puncte pe o latură, cu laturile paralele cu axele de coordonate, poate fi translatat în $(N - L + 1)*(N - L + 1)$ poziţii diferite pe grilă.
Considerăm pentru un pătrat din mulţimea soluţiilor, dreptunghiul minim cu laturile paralele cu axele de coordonate ce conţine acest pătrat. Este uşor să vedem că acest dreptunghi este de fapt un pătrat. Într-un pătrat ce are $L$ puncte pe latura înscrie $L – 2$ pătrate care nu au laturile paralele cu axele de coordonate.
p=. !probleme-cu-puncte-laticiale?img6.JPG 70%!
!probleme-cu-puncte-laticiale?img7.JPG!
Considerăm pentru un pătrat din mulţimea soluţiilor, dreptunghiul minim cu laturile paralele cu axele de coordonate ce conţine acest pătrat. Este uşor să vedem că acest dreptunghi este de fapt un pătrat. Într-un pătrat ce are $L$ puncte pe latură, înscrie $L - 2$ pătrate care nu au laturile paralele cu axele de coordonate.
Astfel vedem că numărul total de pătrate pe o grilă $N × M$ este:
p=. !probleme-cu-puncte-laticiale?img7.JPG 70%!
Sumă după $L$ de la $2$ la $N$ de $(N–L+1) × (N–L+1) × (L–1) =$
suma $L$ de la $1$ la $N-1$ de $(N–L) × (N–L) × L =$ suma cu $L$ de la $1$ la $N–1$ de $LN^2^–2 NL^2^ + L^3^ = N^2^ ×$ suma $L$ de la $1$ la $N-1-2N$ suma $L$ de la $1$ la $N–1$ de $L^2^ +$ suma de $L$ de la $1$ la $N–1$ de $L^3^ = N^2^ ×  N(N-1)/2-2N n(n-1)(2n-1)/6 + [n(n-1)/2]^2^$.
Astfel, vedem că numărul total de pătrate pe o grilă $N * M$ este, succesiv:
<tex>
\begin{array} {lcl} \[ \sum_{L=2}^N {(N-L+1)(N-L+1)(L-1)} \] & = & \[\sum_{L=1}^{N-1} {(N-1)(N-1)L} \] \\ & = & \[\sum_{L=1}^{N-1} {LN^2 - 2NL^2 + L^3}\] \\ & = & \[N^2\sum_{L=1}^{N-1} {L} - 2N\sum_{L=1}^{N-1} {L^2} + \sum_{L=1}^{N-1} {L^3} \] \\ & = & \[n^2\fraq {N(N-1)}{2} - 2n\fraq{N(N-1)(2N-1)}{6} + \left[\fraq{N(N-1)}{2}\rigt]^2 .\] \end{array}
</tex>
* <tex> \displaystyle\sum_{L=2}^{N} (N-L+1)(N-L+1)(L-1) = </tex>
* <tex> = \displaystyle\sum_{L=1}^{N-1} (N-L)(N-L)L </tex>
* <tex> = \displaystyle\sum_{L=1}^{N-1} L*N^2 - 2*L^2*N + L^3 </tex>
* <tex> = \displaystyle N^2 * \sum_{L=1}^{N-1} L - 2 * N * \sum_{L=1}^{N-1} L^2 + \sum_{L=1}^{N-1} L^3 </tex>
* <tex> = \displaystyle N^2 * \frac{N(N - 1)}{2} - 2 * N * \frac{N(N - 1)(2N - 1)}{6} + \left[\frac{N(N - 1)}{2}\right]^2 </tex>
Am folosit formulele cunoscute din manualul de clasa a 10-a:
 <tex> \sum_{k=1}^n k = \frac {n(n+1)} {2} </tex>
 <tex> \sum_{k=1}^n k^2 = \frac {n(n+1)(2n+1)} {6} </tex>
 <tex> \sum_{k=1}^n k^3 = \left[\frac {n(n+1)} {2} \right]^2 </tex>
 
 
* <tex> \displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2} </tex>
* <tex> \displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6} </tex>
* <tex> \displaystyle\sum_{k=1}^{n} k^3 = \left[\frac{n(n+1)}{2}\right]^2 </tex>
 
Această soluţie are complexitatea $O(1)$, fiind o simplă formulă.
h2(#problema5). Problema 5 Counting triangles (ACM ICPC Asia Dhaka 2005/2006)
h2(#problema5). Problema 5: 'Counting triangles':http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3295 (ACM ICPC Asia, Dhaka 2005/2006)
Triunghiurile sunt poligoane cu trei laturi şi cu aria strict pozitivă. Triunghiurile laticiale sunt triunghiuri ce au vârfurile de coordonate întregi. În această problemă va trebui să găsiţi numărul de triunghiuri laticiale ce se pot găsi pe o grilă de dimensiuni $M×N$ $(1  M, N  1000)$. De exemplu pe o grilă de dimensiuni $1×2$ găsim $18$ triunghiuri laticiale distincte după cum vedem în figură:
bq. Triunghiurile sunt poligoane cu trei laturi şi cu aria strict pozitivă. Triunghiurile laticiale sunt triunghiuri ce au vârfurile de coordonate întregi. În această problemă va trebui să găsiţi numărul de triunghiuri laticiale ce se pot găsi pe o grilă de dimensiuni $M * N$ $(1 &le; M, N &le; 1000)$. De exemplu, pe o grilă de dimensiuni $1 * 2$ găsim $18$ triunghiuri laticiale distincte după cum vedem în figură:
!probleme-cu-puncte-laticiale?img14.JPG!
p=. !probleme-cu-puncte-laticiale?img14.JPG 70%!
h3. Rezolvare
Prima idee de rezolvare ar fi de a lua toate combinaţiile de trei puncte distincte dintre cele $N×M$ puncte şi apoi de a elimina oricare trei puncte colineare, dar partea a doua pare greu de realizat în mod eficient.
Vom număra asemănător rezolvării de mai sus numărul de triunghiuri înscrise într-un dreptunghi paralel cu axele de coordonate. Apoi acel dreptunghi îl vom putea translata pe grila de puncte laticiale şi astfel vom putea număra toate triunghiurile posibile.
Prima idee de rezolvare ar fi de a lua toate combinaţiile de trei puncte distincte dintre cele $N * M$ puncte şi apoi de a elimina oricare trei puncte coliniare, dar partea a doua pare greu de realizat în mod eficient. Vom număra, asemănător rezolvării de mai sus, numărul de triunghiuri înscrise într-un dreptunghi paralel cu axele de coordonate. Ulterior, acel dreptunghi îl vom putea translata pe grila de puncte laticiale şi astfel vom putea număra toate triunghiurile posibile.
!probleme-cu-puncte-laticiale?img9.JPG!
p=. !probleme-cu-puncte-laticiale?img9.JPG 70%!
Oricum ar fi un triunghi situat într-un dreptunghi ce este minimal, cel putin un vârf al triunghiului trebuie să fie un vârf al dreptunghiului. Se disting astfel două cazuri: primul în care un vârf al triunghiului este şi vârf al dreptunghiului şi celelalte două puncte sunt situate pe cele două laturi ale dreptunghiului ce nu au ca şi capăt primul punct, iar al doilea caz în care cel puţin două vârfuri sunt vârfuri ale dreptunghiului opuse pe diagonală. Dacă dreptunghiul are $H$ puncte pe verticală şi $W$ puncte pe orizontală, atunci în primul caz vom avea $4 × ((H–1) × (W1) + H1 + W-1)$ triunghiuri, iar în al doilea caz vom avea $2 × (H × W - X)$ unde $X$ e numărul de puncte de coordonate întregi de pe diagonala dreptunghiului. Cum trebuie să numărăm triunghiurile înscrise în fiecare dreptughi pt care $1  H  N$ şi $1  W  M$, obţinem un algoritm de complexitate $O(NM log N)$, acel $log N$ apare la calcularea lui $X$.
Oricum ar fi un triunghi situat într-un dreptunghi ce este minimal, cel puţin un vârf al triunghiului trebuie să fie un vârf al dreptunghiului. Se disting astfel două cazuri: primul în care un vârf al triunghiului este şi vârf al dreptunghiului şi celelalte două puncte sunt situate pe cele două laturi ale dreptunghiului ce nu au ca şi capăt primul punct, iar al doilea caz în care cel puţin două vârfuri sunt vârfuri ale dreptunghiului opuse pe diagonală. Dacă dreptunghiul are $H$ puncte pe verticală şi $W$ puncte pe orizontală, atunci în primul caz vom avea $4 * ((H - 1)(W - 1) + H - 1 + W - 1)$ triunghiuri, iar în al doilea caz vom avea $2 * (H * W - X)$ unde $X$ e numărul de puncte de coordonate întregi de pe diagonala dreptunghiului. Cum trebuie să numărăm triunghiurile înscrise în fiecare dreptughi pentru care $1 &le; H &le; N$ şi $1 &le; W &le; M$, obţinem un algoritm de complexitate $O(N*M log N)$, unde $log N$ apare la calcularea lui $X$.
h2(#problema6). Problema 6 'Dreptunghiuri':problema/dreptunghiuri (preOni 2006 runda 1)
h2(#problema6). Problema 6: 'Dreptunghiuri':problema/dreptunghiuri (preOni, 2006, runda 1)
bq. Clod stă într-o zi plictisit la ora de matematică şi în timp ce profesorul explică la tablă teorema lui Pick, Clod se gândea la o problemă mai interesantă: pentru o grilă de puncte laticiale de dimensiune $N×M$ $(0 < M, N ≤ 400)$ care este numărul de dreptunghiuri cu vârfurile în puncte laticiale. Clod este curios dacă există o formulă pentru această problemă şi ar vrea să ştie soluţia pentru diferite dimensiuni ale grilei, pentru a putea ghici o asemenea formulă.
Ajutaţi-l pe Clod să afle răspunsul!
 
De exemplu pentru o grilă de $3×3$ puncte găsim $10$ dreptunghiuri.
bq. Se dă o grilă de puncte laticiale de dimensiuni $N * M (0 &lt; N, M &le; 400)$. Să se determine numărul dreptunghiurilor cu vârfurile în punctele laticiale. De exemplu, pentru o grilă de $3 * 3$ puncte găsim $10$ dreptunghiuri.
!probleme-cu-puncte-laticiale?img10.JPG!
p=. !probleme-cu-puncte-laticiale?img10.JPG 70%!
h3. Rezolvare
Un dreptunghi care apare în grila de puncte laticiale este mărginit de două drepte verticale la stânga şi la dreapta, şi de două drepte orizontale în sus şi în jos. Acum, dacă vrem pentru patru drepte fixate să ştim câte dreptunghiuri mărginesc ele, ne putem uita la următorul desen.
Un dreptunghi care apare în grila de puncte laticiale e mărginit de două drepte verticale la stânga şi la dreapta, şi de două drepte orizontale în sus şi în jos. Acum, dacă vrem pentru patru drepte fixate să ştim câte dreptunghiuri mărginesc ele, ne putem uita la următorul desen.
!probleme-cu-puncte-laticiale?img11.JPG!
p=. !preoni-2006/runda-1/solutii?drept.jpg 70%!
Dacă dreptunghiul $ABCD$ determinat de cele patru drepte are vârfurile laturile $H$ şi $W$ atunci un dreptunghi $MNPQ$ înscris va împărţi laturile lui in bucăţile $AM$, $MB$ şi $AQ$, $QD$. Evident dacă $MNPQ$ este dreptunghi atunci avem că $AM=PC$, $MB=PD$, $AQ=NC$ şi $QD=NB$. Fie $M’$ proiecţia punctului $M$ pe latura $DC$. Acum folosind teorema lui Pitagora avem că:
$AQ^2^ + AM^2^ = MQ^2^$
$QD^2^ + DP^2^ = QP^2^$
$MQ^2^ + QP^2^ = MP^2^$
$MM’^2^ = (AQ + QD)^2^$
$M’P^2^ = (PD - PC)^2^$
$MM’^2^ + M’P^2^ = MP^2^$
De aici rezultă că $(AQ + QD)^2^ + (PD – PC)^2^ = AQ^2^ + DQ^2^ + AM^2^ + MB^2^$, astfel obtinem $AQ×QD = AM×MA$, dacă notăm cu $A$ lungimea lui $AM$ şi cu $x$ lungimea lui $AQ$ atunci avem că $QD =  H–A$, iar $MA = W–x$ deci avem că $x^2 – W×x + A×(H–A) = 0$. Dacă îl fixăm pe $A$ atunci trebuie să rezolvăm o ecuaţie de gradul doi în necunoscuta $x$, soluţia trebuie să fie întreagă între $0$ şi $W$.
Astfel in $O(H)$ vom şti numărul de dreptunghiuri înscrise într-un dreptunghi de dimensiuni $H×W$. Acest dreptunghi poate fi pus in $(N–H+1)×(M–H+1)$ locaţii pe o grilă de dimensiune $N×M$. Deci soluţia are complexitate $O(N*M^2^)$, pentru fiecare dreptunghi de dimensiuni $1 ≤ H ≤ N$ şi $1 ≤ W ≤ M$ calculându-se numărul de dreptunghiuri înscrise.
O rezolvare de complexitate $O(N^2^*M^2^)$ în care se căutau soluţiile ecuaţiei printr-un $for$ ar fi luat $60$ de puncte. Rezolvarea directă folosind ecuaţia de gradul doi ia în jur de $80$ de puncte. Algoritmul poate fi optimizat la factorii constanţi, de exemplu avem nevoie de funcţia radical care este cam înceată, precalculând-o obţinem o accelerare a vitezei, altă idee ar fi că numărul de soluţii cu $A ≤ H/2$ este egal cu numărul de soluţii cu $H – H/2 ≤ A$ şi a treia idee de optimizare este că numărul de dreptunghiuri înscrise într-un dreptunghi de dimensiuni $H, W$ este acelaşi cu numărul de dreptunghiuri înscrise intr-un dreptunghi de dimensiuni $W, H$.
Dacă dreptunghiul determinat de cele patru drepte are laturile $H$ şi $W$, atunci un dreptunghi înscris va împărţi laturile lui în bucăţile {$A$}, $B$ şi {$C$}, {$D$}. Acum, folosind teorema lui Pitagora avem că:
h2(#problema7). Problema 7 Paralelograme (Bursele Agora 2005/2006 runda 1)
* $A^2^ + D^2^ = Galben^2^$
* $B^2^ + C^2^ = Verde^2^$
* $Galben^2^ + Verde^2^ = Roz^2^$
* $(A + B)^2^ = Roşu^2^$
* $(C $-$ D)^2^ = Albastru^2^$
* $Roşu^2^ + Albastru^2^ = Roz^2^$
bq. Clod este din nou plictisit la ora matematică şi se joacă desenând pe o foaie cu pătrăţele paralelograme cu vârfurile în colţurile pătrăţelelor. Tot desenând paralelograme, Clod se întreabă câte astfel de paralelograme poate construi dacă ştie că foaia de pătrăţele are $N$ linii şi $M$ coloane $(0 < N, M ≤ 2000)$.
Va trebui să îl ajutaţi să rezolve această problemă.
Pentru $N=2$ şi $M=2$ putem construi $22$ de paralelograme
De aici avem că {$(A + B)^2^ + (C - D)^2^ = A^2^ + B^2^ + C^2^ + D^2^$}. Astfel, obţinem {$AB = CD$}, dar {$B = H - A$}, iar {$D = W - C$}, deci, avem că {$C^2^ - WC + A(H - A) = 0$}. Dacă îl fixăm pe $A$ atunci trebuie sa rezolvăm o ecuaţie de gradul doi în necunoscută {$C$}, iar soluţia trebuie să fie întreagă între $0$ şi {$W$}.
!probleme-cu-puncte-laticiale?img12.JPG!
Astfel, în $O(H)$ vom şti numărul de dreptunghiuri înscrise într-un dreptunghi de dimensiuni {$H * W$}. Acest dreptunghi poate fi pus în $(N - H + 1) * (M - W + 1)$ locaţii pe o grilă de dimensiune {$N * M$}. Deci, soluţia are complexitate {$O(N*M^2^)$}, pentru fiecare dreptunghi de dimensiuni $1 &le; H &le; N$ şi $1 &le; W &le; M$ calculându-se numărul de dreptunghiuri înscrise.
 
O rezolvare de complexitate $O(N^2^*M^2^)$ în care se căutau soluţiile ecuaţiei printr-un for ar fi luat $60$ de puncte. Rezolvarea directa folosind ecuaţia de gradul doi ia în jur de $80$ de puncte. Algoritmul poate fi optimizat la factorii constanţi. De exemplu, avem nevoie de funcţia radical care este înceată, pe care, precalculând-o, obţinem o accelerare a vitezei. Altă idee este că numarul de soluţii cu $A &le; H/2$ este egal cu numărul de soluţii cu $A &ge; H - H/2$, iar a treia idee de optimizare este că numarul de dreptunghiuri înscrise într-un dreptunghi de dimensiuni {$H$}, $W$ este acelaşi cu numărul de dreptunghiuri înscrise într-un dreptunghi de dimensiuni {$W$}, {$H$}.
 
h2(#problema7). Problema 7: 'Paralelograme':problema/paralelograme (Bursele Agora, 2005/2006, runda 1)
 
bq. Se dă o grilă laticială cu $N$ linii şi $M$ coloane, unde $0 &lt; N, M &le; 2000$. Să cere determinarea numărului paralelogramelor cu vârfurile aflate la coordonate numere întregi. De exemplu, pentru $N = 2$ şi $M = 2$ putem construi $22$ de paralelograme.
 
p=. !probleme-cu-puncte-laticiale?img12.JPG!
h3. Rezolvare
Ca să determinăm numărul de paralelograme ce se pot găsi pe o grilă laticială, proprietatea că diagonalele unui paralelogram se înjumătăţesc pare să ne ajute în obţinerea unui algoritm de complexitate $O(N + M)$, dar autorul nu a reuşit să numere într-un mod eficient câte paralelograme sunt degenerate (cu cele patru vârfuri colineare) pentru a putea să le eliminăm din numărul total.
Ca să determinăm numărul de paralelograme ce se pot găsi pe o grilă laticială, proprietatea că diagonalele unui paralelogram se înjumătăţesc pare să ne ajute în obţinerea unui algoritm de complexitate $O(N + M)$. Însă, autorul nu a reuşit să numere într-un mod eficient câte paralelograme sunt degenerate (cu cele patru vârfuri coliniare) pentru a putea să le eliminăm din numărul total.
Din nou putem folosi ideea celui mai mic dreptunghi cu laturile paralele cu axele de coordonate pentru a număra repede o clasă mare de paralelograme de aceiaşi formă.
Avem două cazuri posibile:
Din nou, putem folosi ideea celui mai mic dreptunghi cu laturile paralele cu axele de coordonate pentru a număra repede o clasă mare de paralelograme de aceiaşi formă. Avem două cazuri posibile:
!probleme-cu-puncte-laticiale?img13.JPG!
p=. !probleme-cu-puncte-laticiale?img13.JPG 70%!
Primul în care cele patru puncte sunt pe laturile dreptunghiului iar nici un vârf nu coincide cu vârfurile dreptunghiului, şi al doilea în care există două puncte în vârfuri opuse ale dreptunghiului.
În primul caz, dacă avem poziţiile a două vârfuri fixate pe două laturi consecutive ale dreptunghiului, atunci poziţiile celorlator două vârfuri sunt unic determinate. De aici obţinem că în primul caz avem $(h-2)×(w-2)$ paralelograme.
În al doilea caz dacă fixăm două vârfuri ale paralelogramului în colţurile dreptunghiului, celelalte două vârfuri vor fi simetrice faţă de centrul de greutate al dreptunghiului, trebuie să nu luăm în calcul posibilitatea ca vărfurile să fie pe diagonala dreptunghiului, de aici obţinem $h * w - cmmdc(h-1, w-1) – 2$ posibilităţi.
Primul în care cele patru puncte sunt pe laturile dreptunghiului iar nici un vârf nu coincide cu vârfurile dreptunghiului, şi al doilea în care există două puncte în vârfuri opuse ale dreptunghiului. În primul caz, dacă avem poziţiile a două vârfuri fixate pe două laturi consecutive ale dreptunghiului, atunci poziţiile celorlalte două vârfuri sunt unic determinate. De aici obţinem că în primul caz avem $(h - 2) * (w - 2)$ paralelograme. În al doilea caz, dacă fixăm două vârfuri ale paralelogramului în colţurile dreptunghiului, celelalte două vârfuri vor fi simetrice faţă de centrul de greutate al dreptunghiului. Cum nu trebuie să luăm în calcul posibilitatea ca vârfurile să fie pe diagonala dreptunghiului, obţinem $h * w - cmmdc(h - 1, w - 1) - 2$ posibilităţi.
Astfel am ajuns la următorul algoritm:
Astfel, am ajuns la următorul algoritm:
==code(c) |
long num = 0;
for (long h = 2; h <= N + 1; h++)
  {for (long w = 2; w <= M + 1; w++)
     {laux = (h - 2) * (w - 2) + h * w - cmmdc(h - 1, w - 1) - 2;
      num += (N - h + 1) * (M - w + 1) * laux;
     }
long long num = 0, laux = 0 ;
for (int h = 2; h <= N + 1; h++) {
    for (int w = 2; w <= M + 1; w++) {
        laux = (h - 2) * (w - 2) + h * w - cmmdc(h - 1, w - 1) - 2;
        num += (N - h + 2) * (M - w + 2) * laux;
    }
}
==
Acest algoritm are complexitatea $O(NM log N)$, el nu s-ar fi încadrat în timpul impus, marea parte a calculelor este efectuată în determinarea celui mai mare divizor comun a două numere, având în vedere că numerele folosite sunt între $1$ şi $N$ respectiv între $1$ şi $M$, putem să calculăm o matrice $CMMDC[X][Y]$ unde $1  X  N$ şi $1  Y  M$, această matrice poate fi calculată în $O(NM)$. Astfel complexitatea soluţiei a fost redusă  la  $O(NM)$, mai putem optimiza factorii constanţi ai soluţiei observând că într-un triunghi de dimensiuni $H×W$ pot fi înscrise acelaţi număr de dreptunghiuri ca şi într-un triunghi $W×H$, acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri.
Acest algoritm are complexitatea $O(N*M log N)$ şi nu s-ar fi încadrat în timpul impus, deoarece marea parte a calculelor este efectuată în determinarea celui mai mare divizor comun a două numere. Având în vedere că numerele folosite sunt între $1$ şi $N$ respectiv între $1$ şi $M$, putem să precalculăm o matrice $CMMDC[X][Y]$, $1 &le; X &le; N$ şi $1 &le; Y &le; M$, în $O(N * M)$. Astfel, complexitatea soluţiei a fost redusă la $O(N * M)$. Mai putem optimiza factorii constanţi ai soluţiei observând că într-un dreptunghi de dimensiuni $H * W$ poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un dreptunghi $W * H$. Acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri.
h2(#concluzii). Concluzii
Cititorul poate să încerce aplicarea tehnicilor din articol la alte probleme similare, de exemplu determinarea numărului de patrulatere convexe nedegenerate cu vârfurile puncte laticiale, sau numărului de romburi sau trapeze.
 
Cititorul poate să încerce aplicarea tehnicilor din articol la alte probleme similare precum determinarea numărului de patrulatere convexe nedegenerate cu vârfurile puncte laticiale, sau numărului de romburi sau trapeze.
h2(#bibliografie). Bibliografie
* Buşneag, Maftei, Teme pentru cercurile şi concursurile de matematică ale elevilor, Scrisul Românesc, Craiova, 1983
* Iaglom, Iaglom, Probleme neelementare tratate elementar, ed tehnică, Bucureşti, 1962
* 'WolframMathWorld':http://mathworld.wolfram.com
* 'FAQs':http://www.faqs.org/faqs/graphics/algorithms-faq/
* 'Geometry Algorithms':http://geometryalgorithms.com/Archive/algorithm_0101/
 
# Buşneag, Maftei, _„Teme pentru cercurile şi concursurile de matematică ale elevilor”_, Scrisul Românesc, Craiova, 1983
# Iaglom, Iaglom, _„Probleme neelementare tratate elementar”_, Editura Tehnică, Bucureşti, 1962
# 'WolframMathWorld':http://mathworld.wolfram.com
# 'FAQs':http://www.faqs.org/faqs/graphics/algorithms-faq/
# 'Geometry Algorithms':http://geometryalgorithms.com/Archive/algorithm_0101/

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3853