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

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$.

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.

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/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.

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. Se dă un poligon prin vârfurile sale aflate doar la coordonate naturale. Poligonul nu este neapărat convex şi se găseşte într-un sistem de axe de coordonate pozitive. Se cere să se găsească numărul punctelor aflate strict în interiorul poligonului la coordonate numere întregi.

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.
p=. !probleme-cu-puncte-laticiale?img4.JPG 80%!

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.
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 (Max_X + Max_Y))$.

<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))$.

h2(#problema4). Problema 4 (Marele Premiu Paco, 2000)

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 ca vârfurile lor să aparţină punctelor din grilă. De exemplu, pe o grilă de dimensiuni $3 × 3$ există $6$ pătrate.

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.

p=. !probleme-cu-puncte-laticiale?img5.JPG!

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++) {

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 + 1) * (M - w + 1) * laux;

        num += (N - h + 2) * (M - w + 2) * laux;

    }
}
==

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 ≤ X ≤ N$ şi $1 ≤ Y ≤ 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 triunghi de dimensiuni $H * W$ poate fi înscris 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 ≤ X ≤ N$ şi $1 ≤ Y ≤ 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

3853