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.

 
!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 \\

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.

!probleme-cu-puncte-laticiale?img4.JPG!
 

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.

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.

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

h3. Rezolvare:
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ă.

 
!probleme-cu-puncte-laticiale?img6.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 latura înscrie $L – 2$ pătrate care nu au laturile paralele cu axele de coordonate.

 
!probleme-cu-puncte-laticiale?img7.JPG!
 

Astfel vedem că numărul total de pătrate pe o grilă $N × M$ este:
<tex> \[\sum_{L=2}^{N} {(N-L+1) \cdot (N-L+1) \cdot (L-1)}\] = \[\sum_{L=1}^{N-1} {(N-L) \cdot (N-L) \cdot L}\] = \[\sum_{L=1}^{N-1} {L \cdot N^2 - 2N \cdot L^2 + L^3}\] = N^2 \cdot \[\sum_{L=1}^{N-1} {L}\] - 2N \cdot \[\sum_{L=1}^N-1 {L^2}\] + \[\sum_{L=1}^{N-1} {L^3}\] = N^2 \cdot \frac {N(N-1)} {2} - 2N \cdot \frac {N(N+1)(2N+1)} {6} + {\frac {N(N+1)} {2}}^2 </tex>

Triunghiurile sunt poligoane cu trei laturi şi cu aria strict pozitivă. Triunghiurile laticiale sutn triunghiuri ce au vârfurile de coordinate întregi. În această problemă va trebui să găsiti numarul de triunghiuri laticeale ce se pot găsi pe o grilă de dimensiuni M x N (1 <= M, N <= 1000). De exemplu pe o grilă de dimensiuni 1x2 găsim 18 triunghiuri laticeale distincte după cum vedem în figură:

!probleme-cu-puncte-laticiale?img8.JPG!
 

h3. Rezolvare
Prima idee de rezolvare ar fi de a lua toate combinaţiile de trei puncte distincte dintre cele N x M puncte şi apoi de a elimina orice trei puncte colineare, dar partea a doua pare greu de a fi realizată 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 laticeale şi astfel vom putea număra toate triunghiurile posibile.

 
!probleme-cu-puncte-laticiale?img9.JPG!
 

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 x ((H – 1) x (W – 1) + H – 1 + W - 1) triunghiuri, iar în al doilea caz vom avea 2 x (H x 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.
h2(#problema6). Problema 6 'Dreptunghiuri':problema/dreptunghiuri (preOni 2006 runda 1)

De exemplu pentru o grilă de 3x3 puncte gasim 10 dreptunghiuri.

!probleme-cu-puncte-laticiale?img10.JPG!
 

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.

 
!probleme-cu-puncte-laticiale?img11.JPG!
 

Dacă dreptunghiul ABCD determinat de cele patru drepte are vârfurile laturile H si W atunci un dreptunghi MNPQ înscris va împărti laturile lui in bucatile AM, MB şi AQ, QD. Evident dacă MNPQ este dreptunghi atunci avem că AM = PC, MB = PD, AQ = NC 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

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 construe 22 de paralelograme

Pentru N = 2 şi M = 2 putem construi 22 de paralelograme
 
!probleme-cu-puncte-laticiale?img12.JPG!

h3. Rezolvare

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!
 

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.