Probleme cu puncte laticeale

Probleme cu puncte laticeale

Articolul de fata se va concentra pe probleme in care vor aparea puncte de coordonate intregi care sunt numite puncte laticeale. [1] si [2] contin cate un capitol despre puncte laticeale care desi sunt mai matematice decat acest articol pot fi interesante pentru un elev interesat in pregatirea pentru olimpiada. Sa vedem acum cateva probleme ce au aparut pe la concursurile de programare:

Problema 1:

Sa se determine numarul de puncte de coordonate intregi prin care trece segmentul determinat de punctele (0, 0) si (M, N). De exemplu, pentru M = 9 si N = 12 pe segment vor fi 4 puncte de coronate intregi.

Rezolvare:

Putem considera doar cazurile in care <= N <= M, daca N = 0 atunci evident avem M + 1 puncte pe segment. Astfel trebuie sa rezolvam doar cazul in care 1 <= N <= M.

Evident ca orice punct (x, y) pentru a fi pe segmentul nostru trebuie sa satisfaca ecuatia y = M/N x.Aceasta ecuatie are ca solutie un numar natural doar daca Mx se divide cu N, de aici daca D = cmmdc(N, M) atunci x se divide cu N/D, deci x de forma kN/D => y = kM/D. Pentru ca punctul (x, y) sa apartina segmentului, trebuie ca 0 <= x <= N si 0 <= y <= M astfel 0 <= k <= D. Deci numarul de puncte de pe un segment de la (0, 0) la (N, M) este egal cu cel mai mare divizor comun al numerelor M si N la care adaugam 1. Putem determina acest numar in complexitate in O(log (N + M)).

Problema 2: (USACO)

Se da un triunghi cu varfurile de coordonate intregi. Se cere sa se determine numarul de puncte de coordonate intregi ce se afla in interiorul triunghiului sau pe laturile lui. De exemplu un triunghi cu varfurile de coordonate (1, 5), (5, 1) si (6, 6) are 16 puncte in interior.

Rezolvare:

Pentru un dreptunghi cu laturile paralele cu axele de coordonate de lungime M si latime N avem ca numarul de puncte situate strict in interiorul dreptunghiului este (M - 1) x (N - 1), iar numarul de puncte situate pe laturile poligonului este 2M + 2N. Daca notam cu B numarul de puncte de pe laturi si cu I numarul de puncte situate strict in interiorul unui dreptunghi si cu A aria dreptunghiului, observam ca I + B/2 - 1 = (M - 1) x (N - 1) + M + N - 1 = MxN = A.

In cazul triunghiurilor dreptunghice ce au doua catete vom vedea ca aceasta foruma se pastreaza. Evident avem ca A = MxN/2. Pe ipotenuya triunghiului vom avea D puncte (D = cmmdc(M, N) + 1, dar aceasta nu ne intereseaza pe moment), deci numarul de puncte de pe laturile triunghiului este B = M + N + D - 1.Numarul de puncte I din interiorul triunghiului este numarul de puncte din interiorul dreptunghiului (M-1)x(N-1) din care se scad punctele interioare de pe diagonala D - 2, rezultatul impartindu-se apoi la 2, de aici avem I = ((M-1)x(N-1) - D + 2) / 2. Verificam formula I + B/2 - 1 = (M-1 N-1)/2 - D/2 + 1 + M/2 + N/2 + D/2 + ½ = MN/2. Deci formula se verifica si pe astfel de triunghiuri.

Acum ne uitam la cel mai mic dreptunghi ce contine un triunghi oarecare, acest dreptunghi poate fi impartit in patru triunghiuri din care unul este cel initial, iar celelalte sunt trei triunghiuri dreptunghice pentru care catetele merg de-a lungul liniilor laticeale. Vom vedea ca formula noastra se verifica si pentru triunghiuri oarecare. Notam cu Id numarul de puncte interioare dreptunghiului, Ad aria dreptunghiului si Bd numarul de puncte de pe laturile dreptunghiului, cu I1, I2, I3 numarul de puncte din interiorul celor trei triunghiuri dreptunghice, B1, B2, B3 numarul de puncte de pe laturile celor trei triunghiuri, iar A1, A2 si A3 ariile celor trei triunghiuri. Avem ca I = Id - I1 - I2 - I3 - B + 3 (trebuie sa eliminam punctele de pe laturile triunghiului interior si sa avem grija de varfurile acestui triunghi), B = B1 + B2 + B3 - Bd iar A = Ad - A1 - A2 - A3. De aici avem ca I + B/2 - 1 = Id - I1 - I2 - I3 - B1/2 - B2/2 - B3/2 + Bd/2 - 1 + 3= (Id + Bd/2 - 1) - (I1 + B1/2 - 1) - (I1 + B1/2 - 1) - (I1 + B1/2 - 1) = Ad - A1 - A2 - A3 = A, deci egalitarea este valabila si pentru triunghiuri oarecare.

Acum aria triunghiului cu varfurile (x1, y1), (x2, y2), (x3, y3) o putem afla usor folosind formula lui Heron sau folosind

½ x abs( determinat( (x1, y1, 1), (x2, y2, 1), (x3, y3, 1)).

Numarul de puncte de pe laturile triunghiului poate fi determinat usor folosind formula demonstrata in problema anterioara. Acum folosind formula I + B/2 - 1 = A putem afla numarul I si problema e rezolvata prin intoarcerea numarului I + B. Complexitatea rezolvarii este O(log N) unde N este valoarea maxima a coordonatelor.

Problema 3: Copaci (infoarena)

    Macarie, dupa ce a muncit o viata intreaga, se decide la batranete sa se retraga pe o insula pentru a-si gasi linistea interioara si a se dedica naturii. Astfel el cumpara o insula pe care cultiva pomi fructiferi. Insula poate fi reprezentata ca un poligon (nu neaparat convex) intr-un sistem de axe de coordonate pozitive. Pomii sunt plantati doar la coordonate naturale.

Macarie este interesat de numarul de copaci pe care il poate planta strict in interiorul insulei. In acest scop el va furnizeaza copacii care determina insula (varfurile poligonului).

De exemplu pentru poligonul dat prin varfurile (0, 4), (0, 5), (2, 7), (2, 4), (6, 6) si (4, 0) avem 12 puncte de coordinate intregi situate strict in interiorul poligonului.

Rezolvare:

Formula I + B/2 - 1 = A prezentata mai sus se numeste "Teorema lui Pick", iar ea este valabila si pentru poligoane oarecare. Acest fapt este adevarat pentru ca orice poligon are o diagonala interioara, aceasta diagonala il imparte an doua poligoane distincte, daca notam I1 si I2 punctele interioare celor doua poligoane, B1 si B2 punctele de pe laturile celor doua poligoane, A1 si A2 laturile celor doua poligoane si D numarul de puncte de cooronate intregi de pe diagonala atunci daca egalitatea ar fi fost satisfacuta pentru cele doua poligoane atunci avem ca B1 + B2 = B + 2D - 2, I = I1 + I2 + D - 2. De aici avem A = A1 + A2 = I1 + B1/2 - 1 + I2 + B2/2 - 1 = I1 + I2 + B/2 + D - 1 - 2 = I + B/2 - 1. Astfel putem demonstra prin inductie ca relatia este satisfacuta pentru orice poligon.

Aria unui poligon poate fi calculata usor folosind urmatoarea formula A = suma xi yi+1 - xi+1 yi, unde punctul de indice n+1 este primul punct. Astfel obtinem un algoritm de complexitate O(N log (MaxX + MaxY)).

Problema 4: (Marele Premiu Paco 2000)

Se da o grila de puncte laticeale de dimensiuni NxN, se cere sa se determine numarul de patrate care se pot forma astfel ca varfurile lor sa apartina punctelor din grila.

De exemplu pe o grila de dimensiuni 3x3 exista 6 patrate.

Rezolvare:

Un patrat cu latura ce contine L puncte, ce are laturile paralele cu axele de coordonate poate fi translatat in (N - L + 1) x (N - L + 1) pozitii diferite pe grila noastra.

Consideram pentru un patrat din multimea solutiilor, dreptunghiul minim cu laturile paralele cu axele de coordonate ce contine acest patrat. Este usor sa vedem ca acest dreptunghi este de fapt un patrat. Intr-un patrat ce are L puncte pe latura inscrie L - 2 patrate care nu au laturile paralele cu axele de coordonate.

Astfel vedem ca numarul total de patrate pe o grila N x M este:

Suma dupa L de la 2 la N de (N - L + 1) x (N - L + 1) x (L - 1) =

suma L de la 1 la N -1 de (N - L) x (N - L) x L = suma cu L de la 1 la N - 1 de LN^2 - 2 NL^2 + L^3 = N^2 x 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 x N(N-1)/2 - 2N n(n-1)(2n-1)/6 + [n(n-1)/2]^2.

Am folosit formulele cunoscute din manualul de clasa a 10-a:

Suma cu I de la 1 la N de I = n(n+1)/2

Suma cu I de la 1 la N de I^2 = n(n+1)(2n+1)/6

Suma cu I de la 1 la N de I^3 = [n(n+1)/2]^2

Aceasta solutie are complexitatea O(1), fiind o simpla formula.

Problema 5: Counting triangles (ACM ICPC Asia - Dhaka 2005/2006)

Triunghiurile sunt poligoane cu trei laturi si cu aria strict pozitiva. Triunghiurile laticiale sutn triunghiuri ce au varfurile de coordinate intregi. In aceasta problema va trebui sa gasiti numarul de triunghiuri laticeale ce se pot gasi pe o grila de dimensiuni M x N (1 <= M, N <= 1000). De exemplu pe o grila de dimensiuni 1x2 gasim 18 triunghiuri laticeale distincte dupa cum vedem in figura:

Rezolvare:

Prima idee de rezolvare ar fi de a lua toate combinatiile de trei puncte distincte dintre cele N x M puncte si apoi de a elimina orice trei puncte colineare, dar partea a doua pare greu de a fi realizata eficient.

Vom numara asemanator rezolvarii de mai sus numarul de triunghiuri inscrise intr-un dreptunghi paralel cu axele de coordonate. Apoi acel dreptunghi il vom putea translata pe grila de puncte laticeale si astfel vom putea numara toate triunghiurile posibile.

Oricum ar fi un triunghi situat intr-un dreptunghi ce este minimal, cel putin un varf al triunghiului trebuie sa fie un varf al dreptunghiului. Se disting astfel doua cazuri: primul in care un varf al triunghiului este si varf al dreptunghiului si celelalte doua puncte sunt situate pe cele doua laturi ale dreptunghiului ce nu au ca si capat primul punct, iar al doilea caz in care cel putin doua varfuri sunt varfuri ale dreptunghiului opuse pe diagonala. Daca dreptunghiul are H puncte pe verticala si W puncte pe orizontala, atunci in primul caz vom avea 4 x ((H - 1) x (W - 1) + H - 1 + W - 1) triunghiuri, iar in al doilea caz vom avea 2 x (H x W- X) unde X e numarul de puncte de coordonate intregi de pe diagonala dreptunghiului. Cum trebuie sa numaram triunghiurile inscrise in fiecare dreptughi pt care 1 <= H <= N si 1 <= W <= M, obtinem un algoritm de complexitate O(NM log N), acel log N apare la calcularea lui X.

Problema 6: Dreptunghiuri (preOni 2006 runda 1)

Clod sta intr-o zi plictisit la ora de matematica si in timp ce profesorul explica la tabla teorema lui Pick, Clod se gandea la o problema mai interesanta: pentru o grila de puncte laticiale de dimensiune NxM < M, N <= 400) care este numarul de dreptunghiuri cu varfurile in puncte laticiale. Clod este curios daca exista o formula pentru aceasta problema si ar vrea sa stie solutia pentru diferite dimensiuni ale grilei, pentru a putea ghici o asemenea formula.

Ajutati-l pe Clod sa afle raspunsul!

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

Rezolvare:

Un dreptunghi care apare in grila de puncte laticiale este marginit de doua drepte verticale la stanga si la dreapta, si de doua drepte orizontale in sus si in jos. Acum, daca vrem pentru patru drepte fixate sa stim cate dreptunghiuri marginesc ele, ne putem uita la urmatorul desen.
 

Daca dreptunghiul ABCD determinat de cele patru drepte are varfurile laturile H si W atunci un dreptunghi MNPQ inscris va imparti laturile lui in bucatile AM, MB si AQ, QD. Evident daca MNPQ este dreptunghi atunci avem ca AM = PC, MB = PD, AQ = NC QD = NB. Fie M' proiectia punctului M pe latura DC. Acum folosind teorema lui Pitagora avem ca:

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 avem ca (AQ +   QD)^2 + (PD - PC)^2 =AQ^2 + DQ^2 + AM^2 + MB^2, astfel obtinem AQxQD = AMxMA, daca notam cu A lungimea lui AM si cu x lungimea lui AQ atunci avem ca QD = H - A, iar MA = W - x deci avem ca x^2 - Wx + A(H - A) = 0. Daca il fixam pe A atunci trebuie sa rezolvam o ecuatie de gradul doi in necunoscuta x, solutia trebuie sa fie intreaga intre 0 si W.

Astfel in O(H) vom sti numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H * W. Acest dreptunghi poate fi pus in (N - H + 1) * (M - H + 1) locatii pe o grila de dimensiune N * M. Deci solutia are complexitate O(N*M^2), pentru fiecare dreptunghi de dimensiuni 1 <= H <= N si 1<= W <= M calculandu-se numarul de dreptunghiuri inscrise.

O rezolvare de complexitate O(N^2*M^2) in care se cautau solutiile ecuatiei printr-un for ar fi luat 60 de puncte. Rezolvarea directa folosind ecuatia de gradul doi ia in jur de 80 de puncte. Algoritmul poate fi optimizat la factorii constanti, de exemplu avem nevoie de functia radical care este cam inceata, precalculand-o obtinem o accelerare a vitezei, alta idee ar fi ca numarul de solutii cu A <= H/2 este egal cu numarul de solutii cu A >= H - H/2 si a treia idee de optimizare este ca numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H, W este acelasi cu numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni W, H.

Problema 7: Paralelograme (Bursele Agora 2005/2006 runda 1)

Clod este din nou plictisit la ora matematica si se joaca desenand pe o foaie cu patratele paralelograme cu varfurile in colturile patratelelor. Tot desenand paralelograme, Clod se intreaba cate astfel de paralelograme poate construi daca stie ca foaia de patratele are N linii si M coloane ( < N, M <=

Va trebui sa il ajutati sa rezolve aceasta problema.

Pentru N = 2 si M = 2 putem construe 22 de paralelograme.

Rezolvare:

Ca sa determinam numarul de paralelograme ce se pot gasi pe o grila laticeala, proprietatea ca diagonalele unui paralelogram se injumatatesc pare sa ne ajute in obtinerea unui algoritm de complexitate O(N + M), dar autorul nu a reusit sa numere intr-un mod efficient cate paralelograme sunt degenerate (cu cele patru varfuri colineare) pentru a putea sa le eliminam din numarul total.

Din nou putem folosi ideea celui mai mic dreptunghi cu laturile paralele cu axele de coordonate pentru a numara repede o clasa mare de paralelograme de aceiasi forma.

Avem doua cazuri posibile:

Primul in care cele patru puncte sunt pe laturile dreptunghiului iar nici un varf nu coincide cu varfurile dreptunghiului, si al doilea in care exista doua puncte in varfuri opuse ale dreptunghiului.

In primul caz, daca avem pozitiile a doua varfuri fixate pe doua laturi consecutive ale dreptunghiului, atunci pozitiile celorlator doua varfuri sunt unic determinate. De aici obtinem ca in primul caz avem (h - 2) * (w - 2) paralelograme.

In al doilea caz daca fixam doua varfuri ale paralelogramului in colturile dreptunghiului, celelalte doua varfuri vor fi simetrice fata de centrul de greutate al dreptunghiului, trebuie sa nu luam in calcul posibilitatea ca varfurile sa fie pe diagonala dreptunghiului, de aici obtinem h * w - cmmdc(h - 1, w - 1) - 2 posibilitati.

Astfel am ajuns la urmatorul algoritm:

long num = 0;

for (long h = 2; h <= N + 1; h++)

}

Acest algoritm are complexitatea O(NM log N), el nu s-ar fi incadrat in timpul impus, marea parte a calculelor este efectuata in determinarea celui mai mare divizor comun a doua numere, avand in vedere ca numerele folosite sunt intre 1 si N respectiv intre 1 si M, putem sa calculam o matrice CMMDC[X][Y] unde 1 <= X <= N si 1 <= Y <= M, aceasta matrice poate fi calculata in O(NM). Astfel complexitatea solutiei a fost redusa la O(NM), mai putem optimiza factorii constanti ai solutiei observand ca intr-un de dimensiuni hxw pot fi inscrise acelati numar de dreptunghiuri ca si intr-un triunghi wxh, acest artificiu aproape dubleaza viteza algoritmului. Mentionam ca aceleasi optimizari pot fi facute si la problema cu triunghiuri.

Cititorul poate sa incerce aplicarea tehnicilor din articol la alte probleme similare, de exemplu determinarea numarului de patrulatere convexe nedegenerate cu varfurile puncte laticeale, sau numarului de romburi sau trapeze.

Bibliografie:

[1] Busneag, Maftei, Teme pentru cercurile si concursurile de matematica ale elevilor, Scrisul Romanesc, Craiova, 1983

[2] Iaglom, Iaglom, Probleme neelementare tratate elementar, ed tehnica, Bucuresti, 1962

[3] mathworld.wolfram.com

[4] https://www.faqs.org/faqs/graphics/algorithms-faq/

[5] https://geometryalgorithms.com/Archive/algorithm_0101/