algoritmi şi probleme geometrie computationala

8/3/2019 Algoritmi i probleme geometrie computationala

1/76

Copie autorizata pentru .campion

\

Sergiu CORLAT

Algoritmi i problemede geometrie computaional


2/76


Aprobat la edina Senatului Universitii de Stat dinTiraspol din 26 ianuarie 2009.

Toate drepturile asupra acestei ediii aparin autorului.

Reproducerea integral sau parial a textului sau ailustraiilor din aceast ediie este permis doar cu acor-dul scris al autorului.

Autor: Sergiu Corlat, lector superior, UST

Recenzeni: Andrei Braicov,doctor, confereniar universitar, UST

Emanuela Cerchez,

profesor gradul I, Liceul de Informatic

Grigore Moisil, Iai

Redactor: Tatiana Rusu

Coperta: Valentina Stratu

Sergiu Corlat, 2009 EdituraPrut Internaional, 2009

Editura Prut Internaional, str. George Enescu, nr. 6,bl.1, Chiinu MD 2064Tel.: 75 18 74, 74 93 18; fax: 50 87 20; e-mail: [email protected]

CZU 519.6+514 C15

ISBN 978-9975-69-377-6


3/76


Cuprins

Introducere 5

1. Transformri de coordonate 7

1.1. Deplasri i rotaii 71.2. Coordonate polare 91.3. Implementri 10

2. Intersecii 12

2.1. Intersecia dreptelor 122.2. Intersecia dreptei cu un segment 142.3. Intersecia segmentelor 16

3. nfurtoarea convex 17

3.1. Algoritmul elementar 173.2. Algoritmul Graham 20

4. Triangularizri 26

4.1. Un algoritm greedy pentrumulimi de puncte 26

4.2. Triangularizarea poligoanelor convexe 28

4.3. Triangularizarea poligoanelor simple 29

5. Apropiere i apartenen 31

5.1. Cea mai apropiat pereche de puncte 315.2. Apartenena punctului la un domeniu 355.3. Poligonul i diagrama Voronoi 395.4. Nuclee 44


4/76


6. Probleme geometrice de concurs 48

6.1. Robot 486.2. Robot II 506.3. Piatra 526.4. Carcasa 546.5. Turnuri 566.6. Atac 576.7. Evadare 616.8. Arcai 62

6.9. Cetate 686.10. Druizi 69

Notaii 75Bibliograe 76


5/76

5


Introducere

Geometria computaional constituie una din ramurile

importante ale matematicii aplicate moderne. Pornindde la cercetarea unor elemente geometrice simple (punct,segment, dreapt), se ajunge la o modelare complex agurilor geometrice n plan i a corpurilor n spaiul tri-dimensional.

Algoritmii geometriei computaionale stau la baza tutu -ror aplicaiilor de proiectare i modelare grac (aplicaii

CAD, procesoare de grac vectorial, aplicaii de modelare3D). Fr ei ar imposibil proiectarea construciilor ar-hitecturale moderne, realizarea proiectelor GPS, apariiamajoritii absolute a produselor cinematograce de suc-ces din ultimii ani. Enumerarea domeniilor de aplicarepoate continuat la nesfrit.

Domeniul vast de aplicare i multitudinea fenome-

nelor i situaiilor reale, descrise n termenii geometrieicomputaionale, au impus apariia unor probleme geome-trice n cadrul concursurilor de programare de cele maidiferite nivele.

Prezenta lucrare este conceput ca un curs de iniiere nalgoritmii de geometrie computaional pentru studeniifacultilor de prol, pentru profesorii de informatic,precum i pentru elevii claselor liceale, participani laconcursurile naionale i internaionale de programare.

Un alt scop este de a-i forma cititorului abiliti deanaliz i proiectare a algoritmilor. n acest sens, algo-ritmii i soluiile problemelor sunt nsoite de descrieriale structurilor de date, fragmente de cod, de calcule alecomplexitii.


6/76

6


Cu toate c aparatul matematic necesar pentru re-zolvarea problemelor de geometrie computaional esterelativ simplu, implementarea acestuia este nsoit de

necesitatea cercetrii unui numr considerabil de cazurispeciale. Acesta este un motiv pentru care problemele degeometrie computaional se consider printre cele maidicile, n special n condiii de concurs.

Cercetarea i optimizarea soluiilor propuse pentruunele din problemele prezente n lucrare i vor permitecititorului s capete o experien necesar la comparti-

mentul rezolvare de probleme i, nu n ultimul rnd, lagenerarea testelor pentru vericarea soluiilor.La baza lucrrii se a o serie de articole publicate

pe parcursul ultimilor ani n revista de matematic iinformatic Delta, materiale i probleme elaborate ncadrul colilor de var la informatic (ediiile anilor2001, 2002), precum i probleme propuse la concur-

sul de pregtire continu la informatic .campion(campion.edu.ro).in s aduc sincere mulumiri tuturor celor care au

contribuit la apariia acestei cri, n special colectivuluiCatedrei de Informatic i Tehnologii Informaionale aUniversitii de Stat din Tiraspol.

Ianuarie2009 Sergiu Corlat


7/76

7


1. Transformri de coordonate

1.1. Deplasri i rotaiiRezolvarea oricrei probleme de geometrie computa-

ional ncepe (dac e necesar) cu deplasarea coordonate-lor elementelor cercetate (de cele mai dese ori, ale puncte-lor) ntr-un domeniu potrivit al sistemului de coordonate(de obicei, n cadranul unu). n unele cazuri, deplasareapoate nsoit i de rotaia sistemului de coordonate.

Fie ntr-un sistem cartezian de coordonate un punct pde coordonate (x,y). Deplasarea de coordonate de-a lungulaxei Ox cu o valoare dat a implic o modicare a coordo-natelor punctului conform formulelor:

,

.

x x a

y y

= + =

n cazul deplasrii de-a lungulaxei Oy cu valoarea b, transformareade coordonate va dat de sistemul:

,

.

x x

y y b

= = +

Modicarea combinat a coordo-

natelor cu a dup axa Ox i b dupOy va dat de sistemul:

,

.

x x a

y y b

= + = +

Urmtorul tip de transformare este rotaia cu un unghia punctului (punctelor) fa de originea sistemului decoordonate (g. 1.1).

Fig. 1.1. Rotaia punctuluicu un unghi


8/76

8


n unele cazuri,operaia poate re-alizat invers: prin

rotaia originii siste-mului de coordonatefa de un punct (sausistem de puncte) dat.

Atunci exist patrunumere a, b, c, d, carepermit de a trece uni-

voc coordonatele ( , )x y n ( , )x y , utilizndsistemul de ecuaii:

,(1.1)

.

x ax by

y cx dy

= + = +

Pentru a determina acest cuadruplu de numere, pot

folosite punctele (1, 0) i (0, 1).Se observ c la rotaia cu un unghi punctul de coor-donate (1, 0) trece n punctul (cos ,sin ) , iar punctul decoordonate (0, 1) n ( sin ,cos ) (g. 1.2).

Dup substituia acestor valori, n calitate de coecieniai sistemului (1.1) se obine:

=

=

=

=

x a

y c

a

c

cos ,

sin .

Analog: =

=

=

=

x b

y d

b

d

sin ,

cos .

Fig.1.2. Determinarea cuadruplului a, b, c, d fo-losind punctele (1, 0) i (0, 1)


9/76

9


Astfel, sistemul de ecuaii pentru rotaia cu un unghi a unui punct arbitrar n jurul originii sistemului de co-ordonate ia forma:

= = +

x x y

y x y

cos sin ,

sin cos .

n cazul n care rotaia cu unghiul a punctului decoordonate ( , )x y este efectuat fa de punctul de coordo-nate 0 0( , )x y , diferit de originea sistemului de coordonate,nti se transfer originea sistemului de coordonate n

centrul de rotaie, apoi se efectueaz rotaia n jurul noiiorigini a sistemului de coordonate: =

= +

x x x x y y

y y x x y y

0 0 0

0 0 0

( ) cos ( ) sin

( ) sin ( ) cos

sau = +

= + +

x x x x y y

y y x x y y

0 0 0

0 0 0

( ) cos ( ) sin

( ) sin ( ) cos

1.2. Coordonate polare

Problemele n care apare necesitatea parcurgerii uneimulimi de puncte , 1,i p i N = de coordonate (xi, yi) dupunghiurile formate de vectorii

iOp

cu axa Ox se rezolvmai simplu n coordonate

polare, unde ecare punct peste determinat de perechea( , )r , unde r este distanade la punct pn la origineasistemului de coordonate, iar unghiul format de vecto-rul Op

cu axa Ox (g. 1.3). Fig. 1.3. Coordonatele polare alepunctului de coordonate carteziene

(x, y)


10/76

10


Trecerea de la coordonatele carteziene (x, y) la cele po-lare este determinat de urmtoarele formule [1, p. 77]:

r x y

xy

y

x

yy

x y

x y

= + =

>

+

= maxx then

begin maxx:=drag[i].x; imax:=i; end;

{2. separarea in submultimi}

nsus:=1; njos:=1;

sus[1]:=drag[imin]; jos[1]:=drag[imin];

for i:=1 to n do

if not (i in [imin, imax])then

if sarrus(drag[imin],drag[imax],drag[i])


25/76

25


while i0 then i:=i+1

else beginrem:=true;

for j:=i to nsus-1 do

sus[j]:=sus[j+1];

dec(nsus);

end;

end;

until not rem;

{si jos}

repeatrem:=false; i:=2;

while i


26/76

26


4. TriangularizriDin punct de vedere geo-

metric, triangularizarea T(S)a mulimii de puncte S esteo divizare a nfurtoareiconvexe Q(S) n triunghiuri.Suplimentar, se vor respecta

condiiile:a) vrfri ale triunghiurilorpot numai punctedin S;

b) toate punctele mulimiiSvor utilizate n calitate de vrfuri (g. 4.1).

4.1. Un algoritm greedypentru mulimi de puncte

Fie mulimea de puncte SiN=|S|. Fiecare punct p S este descris prin coordonatele sale carteziene ( , )x y . Tri-angularizarea T(S) poate cercetat ca un graf planar cumulimea de noduri S. Prin urmare, numrul de laturiM n S este proporional cu N (conform formulei Euler,

3 6M N ).O soluie simpl n plan este generarea tuturor seg-mentelor posibile cu extremiti n S, sortarea lor duplungime, apoi adugarea consecutiv n triangularizare.n proces se veric dac latura curent intersecteaz la-turile adugate anterior. Dac interseciile lipsesc, laturaeste adugat, n caz contrar, se trece la cercetarea laturii

urmtoare.

Fig. 4.1. Triangularizarea unei mul-imi de puncte


27/76

27


Numrul total de laturi posibile pe punctele din Seste2 2N . Fiecare latur poate cercetat ca un segment de-

scris prin extremitile sale:

type segment=recordp1,p2:nod; l:real;

end;

Prin urmare, vericarea interseciei laturilor poate realizat folosind o procedur identic cu procedura devericare a interseciei segmentelor ( 2.3).Function intersect (A,B: segment): boolean;

Begin

if

sarrus(A.p2,A.p1,B.s1)*sarrus(A.p2,A.p1,B.s2) 0 and sarrus(B.s2,B.s1,A.p1)*Sarrus(B.s2,B.s1,A.p2) 0then

intersect:= true else intersect:= false

End;

Calculul distanei3 dintre dou puncte ,i j p p S (lungi-mea laturii) poate realizat printr-o funcie elementar:Function distant (p[i],p[j]: nod): real;

Begin

distant:= sqrt(sqr(p[i].x-p[j].x)+ sqr(p[i].y-p[j].y));

End;

Pseudocod

Pas 1 m 0

Pas 2 for i 1 to N do for j 1+i to N do Begin m

Latura[m].l distant(p[i],p[j])Latura[m].st p[i]Latura[m].n p[j]

End;

Pas 3 qsort(Latura,m);

3 Pentru dou puncte a, b date prin coordonatele ( , ), ( , )a a b bx y x y ,2 2

( , ) a b a bd a b x x y y= + .


28/76

28


Pas 4 k 0

Pas 5 for i 1 to M do begin

z false for j 1 to k doif intersect(Latura[i],Triang[j])

then z true if NOT z then

begin

k ; Triang[k] Latura[i] end;

end;

Numrul total de laturi generate este proporionalcu 2N . Sortarea lor va necesita un numr de operaiiproporional cu 2 log( )N N . Complexitatea pasului 5 estedeterminat de numrul de vericri ale interseciilor,care nu depete 3N . Prin urmare, complexitatea algo-ritmului greedy este 3( )O N , ceea ce las de dorit pentruvalori mari ale lui N.

4.2. Triangularizarea poligoanelor convexe

Este o problem elementar, care poate rezolvat ntimp liniar.

FiePun poligon convex, datprin lista vrfurilor p

1, ... ,p

Nn

ordinea parcurgerii lor. Pentrua construi o triangularizare nP, este sucient s e constru-ite segmentele diago nale 1 3p p ,..., 1 1Np p (g. 4.2). Numruldiagonalelor este proporionalcu N (numrul de vrfuri alepoligonului). Construirea uneidiagonale necesit un numr

Fig. 4.2. Triangularizarea unui po-

ligon convex


29/76

29


constant de operaii. Triangularizarea poligonului convexpoate util pentru calculul ariei lui. Aria poligonului esteegal cu suma ariilor triunghiurilor din triangularizare.

4.3. Triangularizarea poligoanelor simpleMetoda greedy

n cazul poligoanelor simple nu este posibil de a realizadirect metoda din compartimentul precedent, deoareceapar dou condiii suplimentare care trebuie vericate:

1) aparine oare latura curent poligonului sau exte-riorului poligonului triangularizat;

2) laturile care formeaz frontiera poligonului urmea-z s e incluse n triangularizare indiferent de loculocupat n lista distanelor.

Vericarea primei condiii este echivalent cu verica-rea apartenenei mijlocului laturii la poligon. Algoritmul

care rezolv aceast problem este prezentat n 5.1.Problema a doua se rezolv elementar: prin includerealaturilor ce formeaz frontiera P n nceputul listei caredescrie triangularizarea.

Fie P un poligon simplu, dat prin lista de vrfurip

1, ...,p

N, n ordinea parcurgerii lor. Algoritmul greedy va

descris de urmtorul pseudocod:

Pas 1 m 0

Pas 2 for i 1 toNdofor j 2+i toNdo

Begin

m Latura[m].l distant(p[i],p[j])


30/76

30


Latura[m].st p[i]Latura[m].n p[j]

End;

Pas 3 qsort(Latura,m);Pas 4 for i 1 to N-1 do

Begin

Triang[i].st p[i]Triang[i].n p[i+1]

End;

Triang[N].st p[N]Triang[N].n p[1]

k N

Pas 5 for i 1 to M doBeginz false

for j 1 to k do if intersect(Latura[i],Triang[j])

then z true if NOT z then

Begin

x,y middle(Latura[i]) if apart(x,y,P)then

Begin

k ; Triang[k] Latura[i] End;

End;

End;

Calculul coordonatelor mijlocului segmentului necesitun numr constant de operaii:Procedure middle(a: segment; var x,y:real);

Beginx:=(a.st.x+ a.n.x)/2; y:=(a.st.y+ a.n.y)/2;

End;

Vericarea apartenenei unui punct la un poligon are ocomplexitate liniar fa de numrulNde laturi ale aces-tuia. Prin urmare, complexitatea pasului 5 i complexi-tatea total a algoritmului rmne aceeai ca i pentrualgoritmul descris n 4.1.


31/76

31


5. Apropiere i apartenen

Capitolul este consacrat analizei unor probleme geome-trice n plan: determinarea celei mai apropiate perechi depuncte, apartenena punctului la un poligon, construciapoligoanelor cu proprieti prestabilite. Soluiile directe aleacestor probleme sunt relativ simple, dar nu i optime.

5.1. Cea mai apropiat pereche de puncteFie n plan o mulime de

puncte { }1,..., NS s s= . Se ceres se determine o pereche de

puncte (g. 5.1)* *, , :i js s i j

* *

1,...,1,...,

( , ) min ( , ).i j i ji Nj Ni j

d s s d s s==

=

Calculul direct al tuturordistanelor dintre N punctenecesit un numr de operaiiproporional cu 2N :

index1 1; index2 2;min distance(s

1, s

2);

For i1 to N doFor j

1+i to N do

If distance(si, s

j) < min then

Begin

min distance(si, s

j)

index1 i; index2 j; End;

Acelai rezultat poate obinut ntr-un timp mai re-strns, folosind algoritmul optim cu o complexitate de

( log )O N N .

Fig. 5.1. Cea mai apropiat perechede puncte


32/76

32


Algoritmul optim

Pentru a determina ntimp optim cea mai apro-

piat pereche de puncte,poate folosit tehno-logia recursiv desparte istpnete. Ideea majoreste divizarea, la ecarepas recursiv, a mulimiiiniiale n dou submulimi

liniar separabile i rezol-varea problemei pe ecaresubmulime n parte (g. 5.2).

Cazul elementar, care permite calculul direct al soluiei,este mulimea format din dou sau trei puncte. Numrulde operaii la acest pas este constant. Specicul problemeiconst n determinarea soluiei optime la etapa de asam-blare: avnd dou submulimi S

1

i S2

, cea mai apropiatpereche de puncte n 1 2S S poate s e determinat deo pereche 1 2, : ,s s s S s S . Se poate demonstra c, laetapa asamblrii soluiei, numrul necesar de vericri laecare nivel este liniar fa de numrul de puncte din mul-imile asamblate. Numrul de divizri consecutive ale mul-imii n submulimi balansate4 nu va depi log( )N . Dacnumrul de operaii necesare pentru determinarea soluiei

la un nivel de asamblare este proporional cu N, com-plexitatea nal a algoritmului va ( log )O N N . Pentrusoluionarea optim a problemei este necesar o preproce-sare a mulimii: sortarea punctelor dup abscis (se obineirul sortat X) i sortarea punctelor dup ordonata lor (seobine irul sortat Y). Avnd complexitatea ( log )O N N ,sortarea nu modic complexitatea nal a algoritmului.

Fig. 5.2. Divizarea mulimii n submulimiseparabile fa de dreapta l pentru re-zolvarea recursiv a problemei cea maiapropiat pereche de puncte

4 Numrul de elemente din ecare submulime difer cu cel mult 1.


33/76

33


Fie la un nivel de divizare mulimea S, irul Xal ele-mentelor din Ssortate dup abscisax, irul Ycu elemen-tele Ssortate dup ordonatay.

Aparent, procesul de asamblare a soluiei la un niveldat are o complexitate 2( )O N : maxim Npuncte n S1

imaxim Npuncte n S

2, dintre care urmeaz s e calcu-

late distanele. n realitate,numrul de operaii estemult mai mic.

Fie S a fost divizat nsubmulimile S

1

i S2

, pecare au fost determinatedistanele minime 1 i2 , precum i perechilerespective de puncte. Seconsider = min( , )1 2 (g. 5.3).

Pentru determinarea soluiei optime pe 1 2S S este

necesar de a cerceta doar punctele situate n fia delime de la dreapta lcare separ submulimile. Cele-lalte puncte din submulimi se a, evident, la o distanmai mare dect unul de altul i nu pot mbuntisoluia. Aceast restrngere nu garanteaz efectuareaunui numr liniar de operaii,deoarece pentru un punct cer-cetat 1s S n fia poate unnumr de puncte proporional cu

2S . O analiz mai detaliat per-mite excluderea din cercetare atuturor punctelor care se a nexteriorul dreptunghiului de di-mensiunile 2 , asociat pun-ctului s (g. 5.4). Numrul de

puncte ale mulimii S2 care se pot

Fig. 5.3. Determinarea punctelor poten-

iale pentru soluia pe 1 2S S

Fig. 5.4. Zona de cercetare n

S2pentru un punct dat 1s S


34/76

34


aa n aceast zon nu poate mai mare dect 6. Prin urmare,numrul de vericri la etapa de

asamblare nu va depi 6N.Folosind irurile X i Y, se

formeaz irul Y , care coninepunctele din S situate n fia[ , ]l l + , sortate dup y mulimea punctelor care potmbunti soluia. Pentru e-

care element din Y se calcu-leaz distanele doar pn la urmtoarele 8 elemente: elereprezint (n cel mai ru caz) simetric 6 puncte din S

2

plus 6 puncte din S1minus 3 puncte care coincid, minus

punctul cercetat (g. 5.5).

Pseudocod

Preprocesare

X S, sort(X) {sortare dupx}

Y S, sort(Y) {sortare dupy}

Procedure apr2p(S, X, Y)

If 4S thenbegin formeaz 1 2 1 2 1 2, , , , ,S S X X Y Y

min (apr2p( 1 1 1, ,S X Y),apr2p( 2 2 2, ,S X Y ))

formeaz Y fori 1toY do

forj 1to8do ifdistance( Y [i], Y [i+j]) <

then distance ( Y [i], Y [i+j]) return

end else return distana minim n S{calculat direct}

Fig. 5.5. Numrul elementelorconsecutive Y care pot modicadistana minim nu depete 9


35/76

35


5.2. Apartenena punctului la un domeniu

Apartenena punctului la un poligon convex

Problema determinrii apar-tenenei unui punct la un poli-gon convex este una simpl ipoate rezolvat cu ajutorul al-goritmilor cercetai anterior. Seobserv uor (g. 5.6) c poziiaunui punct interior fa de e-care din vectorii determinai devrfurile consecutive ale poli-gonului este una i aceeai ladreapta, dac vrfurile sunt par-curse n direcia micrii acelorde ceasornic, i la stnga, ncazul parcurgerii vrfurilor ndirecie opus.

Poziia punctului s fa de un vector i jp p

poate determinat n timp constant ( 3.1). Prin urmare,complexitatea algoritmului este proporional doar cunumrul de laturi ale poligonului. Fie punctuls de coor-donate (x

s, y

s) i poligonul convex

1 2( , , ... , )N P p p p= cuNlaturi, descris prin lista vrfurilor parcurse consecutiv(coordonatele vrfurilor sunt stocate n tabloul liniar dearticole P cu cmpurile x i y). Pentru a simplica imple-mentarea, n lista de vrfuri ale poligonului este inclus unvrf virtual 1 1Np p+ .function apart : boolean;

var i : integer;

function veric_punct(x1,y1,x2,y2,x3,y3:real):boolean;

begin

if x1*y2+x2*y3+y1*x3-x3*y2-x2*y1-y3*x1 > 0 then

veric_punct:=true else veric_punct:=false;

end;

Fig. 5.6. Punctele interioare suntplasate de aceeai parte a vecto-rilor determinai de vrfurile con-secutive ale poligonului, poziiacelor exterioare poate varia.


36/76

36


begin {apart}

apart:=true;

for i:=1 to N do

if not

verifc_punct(p[i].x,p[i].y,p[i+1].x,p[i+1].y,s.x,s.y)

then apart:=false;

end; {apart}

Apartenena punctului la un poligon stelatFie un poligon arbitrar

1 2( , , ... , )N P p p p= cu N laturi.Dac nPexist un punct interi-

or c, astfel nct toate intervalele1 2[ , ],[ , ],...,[ , ]Nc p c p c p aparin

integralP, poligonul se numetestelat (g. 5.7).

n cazul n care punctul in-terior c este cunoscut apriori,determinarea apartenenei unui

punct arbitrar s la poligonul P se reduce la vericareaexistenei unui triunghi5 1,i icp p + 1,i N= , care s coninpunctuls n calitate de punct interior.

Numrul triunghiurilor este N, numrul de operaiinecesare pentru vericarea apartenenei punctului lainteriorul unui triunghi este mrginit de o constant. Prinurmare, complexitatea determinrii apartenenei punctu-lui la un poligon stelat va ( )O N n condiia c punctulc este cunoscut.

Apartenena punctului la un poligon simplu

Problema apartenenei unui puncts la un poligon sim-plu P poate rezolvat prin triangularizarea P i prin

5

VrfulpN+1 este unul virtual i coincide cup1.

Fig. 5.7. P - poligon stelat


37/76

37


vericarea ulterioar a apartenenei s la unul din tri-unghiurile formate n procesul triangularizrii.

Un algoritm mai ecient este bazat pe numrarea

interseciilor ale dreptei orizontale l care trece prinpunctul dats cu laturile poligonuluiP(g. 5.8). Se va cer-ceta partea dreptei spre stngade s. Pentru latura curent sedetermin:

poziia punctului fa deaceasta;

intersecia laturii cu semi-dreapta l.Dac numrul interseciilor

spre stnga de s este impar,punctul se a n interiorul po-ligonului; pentru un numr parde intersecii, punctul se a nexterior. Demonstraia este elementar: la parcurgereaspre stnga, prima intersecie marcheaz intrarea semi-dreptei n interiorul poligonului, urmtoarea ieirea.Fiecare pereche urmtoare de intersecii are aceeaisemnicaie.

Pentru stabilirea interseciei semidreptei cu laturacurent pot utilizate metodele descrise n 2.2.

Cazuri specialeA. Dreapta ltrece printr-un vrfp

ial

poligonuluiPla stnga des. Vr-furilep

i-1i p

i+1se a de pri

diferite ale dreptei l. Numrul deintersecii se incrementeaz cu1.

Fig. 5.8. Numrul de interseciiale semidreptei l cu laturile poli-gonului determin apartenenapunctuluis la poligonulP


38/76

38


B. Dreapta lconine laturapi-1

pi+1

a


i-1ip

i+2se a de pri

diferite ale dreptei l. Numrulde intersecii se incrementeazcu 1.

C. Dreapta l trece printr-un vrfp

ial poligonului P la stnga

de s. Vrfurile pi-1

i pi+1

se ade aceeai parte a dreptei l.

Numrul de intersecii nu seincrementeaz.

D. Dreapta lconine laturapi-1

pi+1

a


i-1ip

i+2se a de aceeai

parte a dreptei l. Numrul deintersecii nu se incrementeaz.

Numrul de laturi procesate este N. Determinareainterseciei laturii cu dreapta l este realizat ntr-unnumr constant de operaii. Procesarea cazurilor specialeeste realizat de asemenea ntr-un numr de operaiimrginit de o constant. Prin urmare, complexitatea al-goritmului este ( )O N .


39/76

39


5.3. Poligonul i diagrama Voronoi

O alt problem de apro-

piere n plan este problemadeterminrii poligonului Vo-ronoi pentru o mulime depuncte.

Fie n plan mulimea depuncte 1{ ,..., }NS p p= . Fie-care punct , 1, ,i p i N = este descris de coordonatelecarteziene (x

i, y

i). Pentru un

punct dat ip S se cere s sedetermine poligonul V(i) careva conine toate puncteleplanului, mai apropiate dep

idect de oricare alt punct

, j i j p S p p (g. 5.9).

Problema generalizatpentru toate punctele mul-imii S este cunoscut subnumele diagrama Voronoi(g. 5.10).

De menionat c pentruunele puncte ale mulimiiS, domeniul determinat depoligonul Voronoi poate unul innit. Se poate demonstra c aceast proprietate oposed punctele care formeaz nfurtoarea convex amulimii S.

Algoritmul direct pentru determinarea poligonuluiVoronoi V(i) se bazeaz pe urmtoarea observaie:

Dreapta l, perpendicular pe segmentul pip

ji care tre-

ce prin mijlocul acestuia, conine punctele egal deprtate

Fig. 5.9. Poligonul Voronoi V(i) pentrupunctulp

i.

Fig. 5.10 Diagrama Voronoi pentru

mulimea S


40/76

40


att depi, ct i dep

j. Punctele mai apropiate dep

idect

depj

vor forma semiplanul determinat de dreapta li careconine punctulp

i.

Fiecare punct p S este descris prin coordonatele salecarteziene (x, y). Prin urmare, pentru perechea de punctep

i,p

j,

mijlocul m al segmentului pip

jva determinat de

punctul de coordonate:

,2

;2

i j

m

i j

m

x xx

y yy

+=

+=

dreapta dcare conine segmentulpip

jva descris

de ecuaiaAx+By+C = 0, unde,

,

;

j i

i j

j i i j

A y y

B x x

C x y x y

=

=

= orice dreapt lperpendicular pe segmentulp

ip

jva

avea ecuaia general de forma Ax+By+C= 0; pentru dreapta l, perpendicular pe segmentulp

ip

ji

care trece prin punctul de mijloc al acestuia, valoa-rea coecientului Ceste: Ay

m Bx

m.

Odat ce este cunoscut ecuaia dreptei l, perpendicu-

lare pe segmentulpipj n mijlocul acestuia, poate deter-minat semiplanulR(j): ( ), ( , ) ( , ).i jp R j d p p d p p <

Atunci1,..,

( ) ( ).j Nj i

V i R j=

=

Pentru realizarea algoritmului poate construit un po-ligonR de restrngere a planului, astfel nct S R . Celmai simplu poligon R este un dreptunghi avnd laturile

paralele cu axele de coordonate, determinat de punctele


41/76

41


diagonale (xmin

,ymin

), (xmax

,ymax

):

1,...,min ( ) 1min i

i Nx x

== ,

1,...,max ( ) 1max ii N

x x=

= + ,

1,...,min ( ) 1min ii Ny y== , 1,...,max ( ) 1max ii Ny y== + .Complexitatea algoritmului direct pentru construirea

poligonului Voronoi V(i) este 2( )O N :Etapa 1: Determinarea poligonului de restrngere

necesit un numr de operaii proporional cuN.Etapa 2: Determinarea ecuaiei dreptei l, perpendi-

culare pe segmentul pip

j, necesit un numr de operaii

mrginit de o constant.Etapa 3: Determinarea interseciei dreptei l cu poli-

gonulR i restrngerea ulterioar a acestuia necesit unnumr de operaii proporional cu numrul de laturi alepoligonuluiR (nu mai mare dectN).

Etapele 23 se repet pentru toate punctele, ip S p p . Prin urmare, numrul de operaii nece-

sare pentru determinarea poligonului Voronoi va proporional cu 2N .

Nu este ecient de a aplica direct algoritmul descrisanterior pentru determinarea diagramei Voronoi: com-plexitatea lui crete pn la 3( )O N .

Pentru realizarea ecient a algoritmului de determi-nare a diagramei Voronoi se aplic tehnica divizrii con-

secutive a problemei n mulimi liniar separabile, pn laatingerea cazurilor elementare, i asamblarea ulterioara soluiei [12, pag. 258 269].

Fie 1 2S S S= i au fost construite diagramele Voronoi

1 2( ), ( ) DV S DV S (g. 5.11). Pentru asamblarea soluieivor realizate urmtoarele etape:

Etapa 1: Determinarea vectorilor de intrare (ieire) ailanului de concatenare: se construiesc laturile lips (dou


42/76

42


la numr) pentru nf-urtoarea convexcomun a mulimii

1 2S S , se determinmijloacele acestor la-turi m

1, m

2. Prin punc-

tele m1, m

2se traseaz

vectorii perpendicularipe laturile adugate lanfurtoarea conve-

x. Pentru latura supe-rioar vectorul esteorientat spre latur,pentru cea inferioar de la ea (g. 5.12). Dinnfurtoarea convexpentru 1 2S S sunteliminate lanurile in-terioare de laturi alenfurtoarelor sepa-rate pentru S

1i S

2.

Etapa 2: Construirealanului de concatenare.Construcia lanului n-cepe pe vectorul superi-

or, dintr-un punct careprecede toate intersec-iile vectorului cu razelediagramelor construiteanterior.

Lanul se traseazde-a lungul vectorului,

pn la intersecia cu

Fig. 5.13. Construirea lanului de conca-tenare

Fig. 5.11. Diagramele VoronoiDV(S1) i DV(S

2)

pn la concatenare.

Fig. 5.12 Construirea

nfurtoarei convexe

pentru Sprin adugarea

laturilor. Trasarea vecto-

rilor de intrare (ieire) ai

lanului de concatenare


43/76

43


una din laturile diagramelorDV(S1) sauDV(S

2). n punctul de

intersecie direcia vec torului se modic (g. 5.13).Modicarea direciei lanului este determinat de modi-

carea perechii de puncte ntre care se traseaz acesta. Fie,iniial, lanul marcheaz frontiera dintre punctele p

ii

pj. Atingerea unei laturi a diagramelor construite anterior

semnic e nlocuireapi

prinpk(dac latura atins separ

punctulpidep

k), e nlocuireap

jprinp

k(dac latura atins

separ punctulpj

depk). Direcia nou a lanului de conca-

tenare este determinat de perpendiculara pe segmentul

ce unete perechea nou creat i care trece prin punctul demijloc al acestuia. Procesul ia sfrit n momentul atingeriivectorului inferior al lanului de concatenare.

Etapa 3: Modicarea laturilor diagramei (g. 5.14).Laturile innite (semidrepte) intersectate de lanul deconcatenare se transform n segmente delimitate deoriginea semidreptei i punctul de intersecie a acesteiacu lanul de concatenare, construit la etapa 2.

Laturile nite (segmentele) i modic unul din punc-tele extreme, acestaind nlocuit prinpunctul de interseciecu lanul de conca-tenare.

Laturile dinDV(S1),

situate integral ndreapta de lanul deconcatenare, i latu-rile din DV(S

2), situ-

ate integral n stngaacestuia, se excluddin diagrama nal

pentru 1 2S S .Fig. 5.14. Concatenarea diagramelor


44/76

44


Cazul elementar se obine pentru 2 3S . Proce-sarea acestuia este realizat printr-un numr de operaiimrginit de o constant.

Divizarea consecutiv a mulimii pentru obinerea ca-zurilor elementare necesit o sortare prealabil a punc-telor din Sdup abscisa lor. Complexitatea preprocesriieste ( log )O N N . Numrul de divizri consecutive alemulimii curente n dou submulimi aproape egale6este proporional cu log( )N . Pentru concatenarea solu-iilor pariale, n cazul alegerii structurii de date adec-

vate7

, este necesar un numr de operaii proporional cunumrul total de laturi din soluiile pariale. Deoarecediagrama Voronoi este o divizare planar a unei mulimidin Npuncte, numrul de laturi va proporional cu N.Prin urmare, complexitatea total a algoritmului optimeste ( log )O N N .

5.4. Nuclee

Printre problemele geometrice de calcul se numr iproblema determinrii nucleului po-ligonului simplu. Nucleul unui poli-gon simpluPeste, n general, formatdin mulimea de puncte Q P , ast-fel nct:

, , [ , ]x Q y P x y P .Cu alte cuvinte, nucleul poligonu-

lui este mulimea de puncte ale po-ligonului, astfel nct oricare dintre

6S1

este aproape egal cu S2, dac 1 2 1S S .

7 O structur optim este lista bidirecional a laturilor.

Fig. 5.15. Poligon simplucu nucleu (partea colorata poligonului)


45/76

45


ele, ind unit cu orice alt punct alpoligonului, formeaz un segment ceaparine n ntregime poligonului (g.

5.15).Nu ntotdeauna un poligon simplu

are nucleu nevid (g. 5.16).Nucleul poligonului (dac el exist)

este i el un poligon, dar, spre deose-bire de poligonul iniial, este ntot-deauna convex.

Algoritmul pentru determinareanucleului unui poligon simplu

Date iniiale. Fie un poligon simplu Pcu Nvrfuri.Se consider c poligonul este descris prin lista vrfurilorsale 1 2 1( , ,..., , )N N p p p p , parcurse n direcia micriiacelor de ceasornic. Fiecare vrfp

ieste descris de coordo-

natele sale (xi, y

i).

Algoritmul de determinare a nucleului necesit oconstrucie secundar: un poligon convex Q care, iniial,conine poligonul P. Pentru determinarea poligonului Qpot abordate dou metode:

a) construirea nfurtoarei convexe pentruP;b) construirea unui dreptunghi care conineP.

Metoda a doua este mult mai simpl. Ea se reduce ladeterminarea, pentru coordonatele vrfurilorP, a valori-lor minime i maxime ale abscisei i ale ordonatei. ncalitate de Q poate considerat dreptunghiul cu vrfuri-le max max( 1, 1)x y+ + , max min( 1, 1)x y+ , min min( 1, 1)x y ,

min max( 1, 1)x y + . Extinderea valorilor extreme nu este ocondiie obligatorie.

Fig. 5.16. Poligon simplufr nucleu


46/76

46


Dup construirea poligonului Q poate determinatnemijlocit nucleul. Metoda (sau cel puin descrierea ei nlimbajul uman) este foarte simpl:

Se analizeaz consecutiv laturile poligonului P, indparcurse n direcia micrii acelor de ceasornic. Laturacurentp

ip

i+1se cerceteaz ca o dreapt l. Se determin

partea poligonului Q care se a n stnga vectorului1i ip p +

i se exclude din Q. Dac poligonul Q este situat

integral n stnga vectorului 1i ip p +

, cercetarea ia sfrit poligonulPnu are nucleu.

Procedeul se repet pn nu sunt analizate toate la-turile poligonuluiP.n nal, Q conine nucleul luiP(g. 5.17).

Fig. 5.17. Construirea consecutiv a nucleului poligonului simplu

PseudocodPas 1 Iniializare

La sfritul listei de vrfuri (duppN

) se adaugvrful virtual p

N+1. Se construiete poligonul Q

(nucleul iniial), conform uneia din metodele de-scrise anterior. 1.i


47/76

47


Pas 2 Procesarea laturii i

Fie 1 2( , ,... )kQ q q q= . Pentru dreapta lce coninelatura i a poligonului Pdenit de vrfurile p

i

,

pi+1

se determin punctele de intersecie cu poli-gonul Q, precum i laturile intersectate. Fie d

1,

d2punctele de intersecie a dreptei l cu Q, iar la-

turile intersectate qj

qj+1

i qk

qk+1

.8

a) Se formeaz poligoanele1 1 1 2( , , ... , , )j kQ d q q d +=

i 2 2 1 1 1( , , ... , , , ... , , )k N jQ d q q q q d += .

b) Se determin * 1 2{ , }Q Q Q care se a n dreaptavectorului 1i ip p +

.

c) *Q Q

Pas 3 Repetare

if i N< then begin i goto pas 2 end elseSTOP Q este nucleul.

Complexitatea algoritmului este 2( )O N . Se preluc-reazNlaturi ale poligonuluiP. Pentru ecare latur severic intersecia cu maximum Nlaturi ale poligonuluiQ. Fiecare intersecie este determinat ntr-un numr deoperaii mrginit de o constant.

8 Dac dreapta nu intersecteaz poligonul Q, se veric doar poziia Q

fa de 1i ip p +

. Dac poligonul e poziionat n stnga, nucleul nal este

vid, altfel Qnu se modic la acest pas.


48/76

48


6. Probleme geometrice de concurs

6.1. RobotUn robot punctiform poate executa instruciuni de depla-

sare n 8 direcii (1 nord, 2 nord-est, 3 est, 4 sud-est,5 sud, 6 sud-vest, 7 vest, 8 nord-vest). Lungimea pa-sului robotului este 1 pentru direciile 1, 3, 5, 7 i 2 pen-tru direciile 2, 4, 6, 8. Numrul de pai efectuai n direciaaleas este un parametru al instruciunii de deplasare.

Fiind dat un set de instruciuni, s se determine coordo-natele punctului nal n care se va deplasa robotul.

Astfel, pentru setul(1,3) (3,1) (1,1) (3,3)(5,2) (7,1) coordonatelenale vor (3,2).

S se scrie un program care, dup un set de instruciuni,s determine coordonatele punctului nal n care se va de-plasa robotul. Se consider c axa Ox e orientat spre est, iarOy spre nord. Iniial robotul se a n originea sistemuluide coordonate (0,0).

Date de intrarePrima linie a ierului de intrare conine numrul N

numrul de instruciuni (1 N 40). Urmtoarele N liniiconin instruciunile propriu-zise numrul direciei (unnumr ntreg de la 1 la 8) i numrul de pai (un numrntreg de la 1 la 1000), separate prin spaiu.

Date de ieireUnica linie a ierul de ieire va conine dou numere

ntregi x i y, separate prin spaiu, coordonatele punctuluinal n care se deplaseaz robotul.


49/76

49


Exemple

date.in date.out

6 3 2

1 33 1

1 1

3 3

5 2

7 1

1

8 10 -10 10

Rezolvareprogramp01;

var I,N:integer;

D,L,X,Y:Longint;

begin

assign(Input,date.in); reset(Input);

read(N);

X:=0; Y:=0; {xarea pozitiei initiale}

for I:=1 to N do

begin {modelarea deplasarii}read(D,L);

case D of

1: Y:=Y+L; { deplasare nord cu L}

2:begin X:=X+L; Y:=Y+L; end; {nord-est cu L}

3: X:=X+L; {est cu L}

4:begin X:=X+L; Y:=Y-L; end; {sud-est cu L}

5: Y:=Y-L; {sud cu L}

6:begin X:=X-L; Y:=Y-L; end; {sud-vest cu L}

7: X:=X-L; {vest cu L}

8:begin X:=X-L; Y:=Y+L; end; {nord-vest cu L}end;

end;

assign(Output,date.out); rewrite(Output);

write(X, ,Y);

close(Input); close(Output);

end.


50/76

50


6.2. Robot II

Sistemul de comand al unuirobot care poate executa instruc-iuni de deplasare s-a deteriorat.Robotul continu s primeascinstruciuni, dar le interpreteaznu ntotdeauna corect. Fiecareinstruciune este un triplet denumere (u,vx,vy) ntregi pozi-tive. Dac u > 90, atunci robotul

se deplaseaz cu vx dup axa Ox i cu vy dup axa Oy. Dacu 90, robotul se deplaseaz pe un arc de msura u al cercu-lui de centru (vx,vy) mpotriva micrii acelor de ceasornic.Raza cercului este segmentul care unete robotul cu centrulcercului.

S se scrie un program care, dup coordonatele iniialeale robotului i un set dat de instruciuni, determin punctulnal n care va poziionat acesta.

Date de intrarePrima linie a ierului de intrare conine dou numere

ntregi coordonatele iniiale ale robotului. Urmtoarelelinii conin cte o instruciune, format din trei numerentregi, separate prin spaiu.

Date de ieire

Unica linie a ierul de ieire va conine dou numere xi y, separate prin spaiu, coordonatele nale ale robotu-lui, indicate cu cel puin 3 cifre dup virgul.

Exemplu date.in date.out

3 2 -0.653 15.697

130 4 1

45 1 7

91 0 3

60 0 6


51/76

51


Rezolvare

programp02;const pi=3.141592;

type point=record

x,y : real;

end;

var P: point;

alfa,xn,yn:real;

procedure move(var P:point; vx,vy:real);

begin

P.x:=P.x+vx;

P.y:=P.y+vy;

end;

procedure rotate (var P:point; u,vx,vy:real);

var old:point;

begin

old:=P;

P.x:=vx+(old.x-vx)*cos(u*pi/180)-

(old.y-vy)*sin(u*pi/180);P.y:=vy +(old.x-vx)*sin(u*pi/180)+

(old.y-vy)*cos(u*pi/180);

end;

begin

assign(input,data.in); reset(input);

assign(output,data.out); rewrite(output);

readln(P.x,P.y);

while not eof do

begin

readln(alfa,xn,yn);

if alfa>90 then move(P,xn,yn)

else rotate(P,alfa,xn,yn);

end;

writeln(P.x:10:3, ,P.y:10:3);

close(input); close(output);

end.


52/76

52


6.3. Piatra

... i unde nu pornete stnca la vale, sltnd tot mai sus deun stat de om; i trece prin gardul i prin tinda Irinuci, pela capre, i se duce drept n Bistria, de clocotea apa!

Ion Creang. Amintiri din copilrie

Piatra pornit de Ion Creang se rostogolea n liniedreapt, drmnd totul n calea sa. Casa Irinuci aremuli perei, unii nimerind n calea pietrei. Fiind date

coordonatele a dou puncte prin care trece piatra iextremitile segmentelor care descriu baza pereilor ca-sei, s se determine ci perei vor drmai de piatran cdere. Peretele atins ntr-un punct extrem rmne n-treg.

S se scrie un program care determin numrul deperei drmai de piatr.

Date de intrareFiierul de intrare date.in conine N (N < 1000) linii a

cte patru numere ntregi. Prima linie conine descriereaa dou puncte prin care trece piatra, n formax

1, y

1, x

2, y

2

(|xi, y

i|


53/76

53


Exemplu date.in date.out

2 1 9 14 4

2 4 1 8

1 12 3 94 14 6 11

7 14 9 10

9 14 7 16

6 10 8 8

3 6 6 6

4 2 4 5

11 10 12 14

8 6 10 8

12 8 14 4


type point=record x,y: real; end;

segment=record e1,e2: point; end;

var g: array[1..1000] of segment;

l: segment;

n,i,k: integer;

function sarrus(p1,p2,p3:point): real;

begin sarrus:=p1.x*p2.y+p2.x*p3.y+p1.y*p3.x-p3.x*p2.y-p3.y*p1.x-p1.y*p2.x;

end;

begin

assign(input, date.in); reset(input); n:=0;

readln(l.e1.x,l.e1.y,l.e2.x,l.e2.y);

while not eof do

begin

inc(n); readln( g[n].e1.x,

g[n].e1.y,g[n].e2.x,g[n].e2.y); end;

k:=0;

for i:=1 to n do

if

sarrus(l.e1,l.e2,g[i].e1)*sarrus(l.e1,l.e2,g[i].e2) < 0

then inc(k);

assign(output, date.out); rewrite(output);

writeln(k); close(input); close(output);

end.


54/76

54


6.4. Carcasa

Fie o carcas avnd forma

unui poligon simplu. Pentrua poziionat vertical pe osuprafa plan, carcasa trebuies aib centrul de mas situatstrict ntre 2 puncte de contactcu suprafaa. Centrul de maseste ntotdeauna un punct interior al carcasei i nu coin-

cide cu nici un vrf al ei.S se scrie un program care va determina numrulpoziiilor n care poate stabilizat vertical carcasa.

Date de intrarePrima linie a ierului de intrare date.inconine trei

numere ntregi, separate prin spaiu: N numrul devrfuri ale carcasei i

xc, yc coordonatele centrului de

mas.Urmeaz N linii ce conin cte dou numere ntregix

i,y

i

(1000 xi, y

i 1000), separate prin spaiu, coordonatele

vrfurilor poligonului n ordinea parcurgerii lor.

Date de ieireFiierul de ieire date.out va conine un singur numr

ntreg numrul de poziii n care poate stabilizat ver-tical carcasa.

Restricii3 N 1000

1000 xc, y

c 1000


55/76

55


Exempludate.in date.out

10 6 16 3

3 14

13 423 14

33 4

33 14

23 24

13 14

3 24

-7 14

-7 4

Rezolvare

Deoarece carcasa se sprijin pe care-va puncte extreme ale poligonului, pro-blema poate divizat n dou subpro-bleme relativ simple:

1) determinarea nfurtoareiconvexe a vrfurilor poligonului;

2) vericarea dac un triunghi are un unghi obtuz.

Prima subproblem este rezolvat cu ajutorul algorit-mului descris anterior ( 3.2).

Dup determinarea nfurtoareiconvexe, problema poate reformulatn felul urmtor:

Fie un poligon convex Pi un punctinterior c, unit prin linii drepte cu vrfurile poligonului. n

cte dintre triunghiurile formate nlimea construit dinpunctul c se proiecteaz ntr-un punct interior al laturiipoligonului care aparine triunghiului?

Evident, nlimea construit din c se proiecteaz pelatur dac niciunul dintre unghiurile alturate laturii poli-gonului nu este obtuz. Vericarea unghiurilor se realizeazelementar cu ajutorul teoremei cosinusurilor. Complexi-

tatea etapei este liniar dup numrul de vrfuri.


56/76

56


6.5. TurnuriBitlanda este o ar care se extinde permanent, lini-

ar. Frontiera rii reprezint o linie frnt nchis, fr

autointersecii. Pentru a apra frontierele sale, dup e-care extindere, n noile puncte extreme ale frontierei seconstruiesc turnuri de veghe. Exist N turnuri de veghe,date prin coordonatele lor (x

i, y

i) numere ntregi. Regele

Bitlandei, Bytezar, a decis sa trimit la vatr garnizoaneleturnurilor care nu se mai a la hotarele rii.

S se scrie un program care va determina cte turnurivor lipsite de garnizoane.

Date de intrarePrima linie a ierului de intrare conine un numr

ntreg: N (1 N 10000) numrul de turnuri de veghen Bitlanda.

Urmeaz N linii ce conin cte dou numere ntregixi

,yi

(1000 xi, y

i 1000), separate prin spaiu, coordonatele

turnurilor de veghe.

Date de ieireFiierul de ieire va conine un numr ntreg numrul

de turnuri care pot lipsite de garnizoane.

Exempluturn.in turn.out10 52 13 46 36 68 510 311 712 69 1115 8


57/76

57


6.6. Atac

Agenia Spaial a planetei Bitterra (ASB) a recepionat unroi meteoritic, care se apropie de planet. Fiecare stat de pe

Bitterra a fost anunat despre pericol i a primit lista punctelorde cdere a meteoriilor, calculate de ASB. Serviciile pentrusituaii excepionale ale ecrui stat urmeaz s determineci meteorii vor cdea pe teritoriul rii. Frontiera oricruistat de pe Bitterra este un poligon convex; meteoriii sunt punc-tiformi. Punctele de pe frontier nu se consider aparinndstatului. Frontiera poate conine mai multe vrfuri consecutive

coliniare.

S se scrie un program care va determina numrul demeteorii ce cad pe teritoriul unui stat dat.

Date de intrarePrima linie a ierului de intrare atac.in conine numrul

n numrul de vrfuri ale poligonului care descrie frontiera

unui stat. Urmtoarele n linii conin descrierea consecutiv avrfurilor frontierei: ecare linie va conine cte o pereche denumere separate prin spaiu coordonatele unui vrf. Urmeazo linie care conine un numr ntreg m numrul de meteorii,apoi m linii, care conin cte dou numere, separate prin spaiu, coordonatele punctelor de cdere a meteoriilor.

Date de ieire

Fiierul de ieire atac.out va conine un singur numr n-treg cel al meteoriilor care cad pe teritoriul statului dat.

Restricii1. Coordonatele vrfurilor poligonului i ale punctelor de

cdere a meteoriilor sunt numere ntregi din intervalul[-1000000, 1000000].

2. 3 n 20000.

3. 2 m 20000.


58/76

58


Exempluatac.in atac.out Explicaie

4 2

2 4

8 46 8

4 6

4

3 5

4 7

5 5

6 7

RezolvareFormularea abstract a problemei este urmtoarea:Fie n plan un poligon convexPcu n vrfuri. n acelai

plan este dat o mulime Mdin m puncte. Se cere s sedetermine cte puncte din Maparin interioruluiP.

Rezolvarea se divide n cteva etape.

1. Se determin un punct interior

al poligonului de coordonate(x

cm, y

cm) (de exemplu, centrul

de mas).

Fiind date coordonatele (xi, y

i),

1,i n= , ale vrfurilor poligonuluiP, coordonatele centrului de maspot calculate dup formula:

1 1, .

n n

i i

i icm cm

x y

x yn n

= == =

2. Fiind dat un punct interior (xcm

, ycm

) al poligonului,se calculeaz unghiurile pe care le formeaz cu axa Oxsemidreptele duse din acesta prin vrfurile (c

x, c

y).


59/76

59


function angle(cx,cy:real): real;

begin

sinus:=(cy -ycm)/ sqrt(sqr(cy-ycm)+sqr(cx-xcm));

cosinus:= (cx -xcm)/ sqrt(sqr(cy-ycm)+sqr(cx-xcm));if cosinus=0 then

if sinus>0 then angle:= pi/2

else if sinus0) and(cosinus>0)

then angle:=arctan(sinus/cosinus);

if (sinus>0) and(cosinus


60/76

60


then begin st:=k; dr:=k+1; end

else begin

if (alfa < a[1].u)

then begin st:=k+1; dr:=n+1; end

else begin st:=1; dr:=k; end;repeat

mj:=(st + dr) div 2;

if a[mj].u >alfa then dr:=mj else st:=mj

until dr=st+1;

end;

5. Se determin poziia centrului de mas i a punctu-lui curent al mulimii M fa de latura determinat.

Dac sunt de aceeai parte, punctul curent esten interior. Pentru determinarea poziiei se

folosete semnul determinantului1 1

2 2

3 3

1

1

1

x y

x y

x y

,

unde (x1, y

1), (x

2, y

2) sunt coordonatele vrfurilor care

determin latura, iar (x3, y3) coordonatele pun ctuluicercetat (respectiv coordonatele centrului de mas).

q:=semn(a[st].x,a[st].y,a[dr].x,a[dr].y,b[i].x,b[i].y);

p:=semn(a[st].x,a[st].y,a[dr].x,a[dr].y,xcm,ycm);

if p*q>0 then inc(s);


61/76

61


6.7. Evadare

Un grup de pinguini a decis s evadeze din grdina

zoologic. n acest scop ei au spat un tunel liniar. Dinnefericire, zidul grdinii zoologice formeaz un poligonsimplu cu N (3N10000) laturi, astfel nct, ieind dintunel, pinguinii nu pot arma cu certitudine dac se an interiorul grdinii zoologice sau n afara ei.

S se scrie un program care, dup coordonatele punc-

telor extreme ale tunelului i coordonatele vrfurilor po-ligonului ce stabilesc perimetrul grdinii zoologice, va de-termina dac evadarea s-a soldat cu succes sau nu.

Date de intrarePrima linie a ierului de intrare evadare.in conine

patru numere ntregi, separate prin spaiu, coordonatelepunctelor extreme ale tunelului. Urmtoarele linii conindescrierea consecutiv a vrfurilor zidului: ecare linie vaconine cte o pereche de numere, separate prin spaiu, coordonatele unui vrf.

Date de ieireFiierul de ieire evadare.out va conine un singur cu-

vnt: DA n cazul n care punctul nal al tunelului este

n afara grdinii zoologice; NU n caz contrar.

RestriciiCoordonatele vrfurilor poligonului i ale punctelor

extreme ale tunelului sunt numere ntregi din intervalul[-1000, 1000].


62/76

62


Exemplu

evadare.in evadare.out explicaie

5 3 7 7 DA

1 22 6

6 4

6 7

7 5

10 4

7 2

3 1

6.8. ArcaiSecretul victoriilor faimo-

sului comandant de oti Mega-Flop este strategia lui dealegere a poziiei arcailor pecmpul de lupt. Cmpul areforma unui poligon simplu ie nconjurat de pduri. Mega-Flop plaseaz arcaii doar pepoziii din care este vzut totcmpul de lupt. Se considerc arcaii vd tot cmpul, dac din orice punct care aparinepoziiei lor de tragere se poate trage cu sgeata n orice altpunct al cmpului. Traiectoria sgeii este liniar. Nimerind

n pdure, sgeata se pierde. Pentru tragere, ecare arcaare nevoie de o unitate de suprafa. Astfel, numrul ma-xim de arcai care pot plasai pe poziii este determinatde aria poligonului din care este vzut toat cmpia.

S se scrie un program care determin numrul maximde arcai care pot plasai pe poziii de tragere n cmpulde lupt.


63/76

63


Date de intrareFiierul de intrarearcas.inva conine pe prima linie un

numr ntreg N numrul de vrfuri ale poligonului sim-

plu care descrie perimetrul cmpului de lupt. Urmeaz Nlinii care conin coordonatele vrfurilor poligonului, par-curse n sensul micrii acelor de ceasornic, cte un vrfpe linie. Linia i+1 conine dou numere ntregi x

i, y

i,

separate prin spaiu, coordonatele vrfului i.

Date de ieire

Fiierul de ieire arcas.outva conine un singur numrntreg numrul maxim de arcai care pot plasai pepoziii.

Restricii3 N 10000 < x

i, y

i 10000

Exempluarcas.in arcas.out

9 11

2 5

3 6

2 7

4 7

6 9

8 6

7 2

5 43 4


type

lat=record x,y:real; end;

pol=array[0..1001] of lat;


64/76

64


var

nuc,camp:pol;

i,nnuc,ncamp:integer;

xint,yint:real;

procedure init;

var square : array[1..5,1..2] of integer;

i: integer;

begin

{initializare nucleu}

nuc[1].x:=0; nuc[1].y:=0;

nuc[2].x:=0; nuc[2].y:=10001;

nuc[3].x:=10001; nuc[3].y:=10001;

nuc[4].x:=10001; nuc[4].y:= 0;

nuc[5].x:=nuc[1].x; nuc[5].y:= nuc[1].y;nnuc:=4;

{ si initializare poligon}

readln(ncamp);

for i:=1 to ncamp do readln(camp[i].x,camp[i].y);

camp[ncamp+1].x:=camp[1].x;camp[ncamp+1].y:=camp[1].y;

end;

function intersect

(al,bl,cl,ad,bd,cd:real;i,j:integer): boolean;

{determin intersecia dreptei i laturii

+ coordonate punctului de intersecie}

begin

{1. dreapta i latura sunt paralele}

if Ad*Bl=Bd*Al then begin intersect:=false; exit; end;

{2. dreapta intersecteaz 2 laturi adiacente n punct

extrem}

if (camp[j+1].x=nuc[i].x) and(camp[j+1].y=nuc[i].y)

then begin

intersect:=true; xint:=nuc[i].x; yint:=nuc[i].y;

exit;

end;

if (camp[j].x=nuc[i+1].x) and(camp[j].y=nuc[i+1].y)

then begin

intersect:=true; xint:=nuc[i+1].x;

yint:=nuc[i+1].y; exit;

end;


65/76

65


{3. Dreapta i latura nu sunt paralele}

if (Ad*BlBd*Al) then

if Al0 then begin

yint:=(Ad*Cl-Cd*Al)/(Bd*Al-Ad*Bl);

xint:=(-Bl*yint-Cl)/Al; end

else

begin yint:=-Cl/Bl;

xint:=(-Bd*yint-Cd)/Ad;

end;

if (((xint>=nuc[i].x) and(xint=nuc[i+1].x) and(xint=nuc[i].y) and(yint=nuc[i+1].y) and(yint


66/76

66


begin

nr:=nr+1;

inter[nr].x:=xint;

inter[nr].y:=yint;

index[nr]:=i; end;

end;

if nr>=2 then

begin

if sarrus(camp[j],camp[j+1],nuc[index[1]])>=0

then

begin

ii:=1;

copy[1].x:=inter[1].x;

copy[1].y:=inter[1].y;

for k:=index[1]+1 to index[2] do

begin

inc(ii); copy[ii]:=nuc[k];

end;

inc(ii); copy[ii].x:=inter[2].x;

copy[ii].y:=inter[2].y;

nnuc:=ii;

inc(ii); copy[ii].x:=inter[1].x;

copy[ii].y:=inter[1].y; end

else

begin

ii:=0;

for k:=1 to index[1] do

begin inc(ii); copy[ii]:=nuc[k]; end;

inc(ii);

copy[ii].x:=inter[1].x;copy[ii].y:=inter[1].y;

inc(ii);

copy[ii].x:=inter[2].x;copy[ii].y:=inter[2].y;

for k:=index[2]+1 to nnuc do

begin inc(ii); copy[ii]:=nuc[k]; end;

nnuc:=ii; inc(ii); copy[ii]:=nuc[1]

end;

nuc:=copy;

end


67/76

67


else

if sarrus(camp[j],camp[j+1],nuc[1])>=0 then

begin

writeln(0); close(output); halt;

end;end;

function area(a:pol;n:integer):real;

{aria poligonului simplu}

var s:real;

i:integer;

begin

s:=0;

for i:=1 to n do

s:=s+(a[i+1].x-a[i].x)*(a[i+1].y+a[i].y)/2;

area:=s;

end;

{programul principal}

begin

assign(input,arcas.in);

reset(input);assign(output,arcas.out);

rewrite(output);

init;

for i:=1 to ncamp do

cut(i);

writeln(area(nuc,nnuc));

close(input);

close(output);

end.


68/76

68


6.9. Cetate Arheologii din Bitlanda n timpul

spturilor au descoperit nite pietre

aezate oarecum straniu. Ei au ajunsla concluzia ca acestea formeaz frag-mente ale unui zid circular, care ncon-jura o cetate veche.

Pentru a proteja de turiti i decurioi fragmentele descoperite, arheo-logii au decis s le nconjoare cu un gard din plas metalic.

Deoarece este destul de complicat i incomod de a nconjuraecare fragment, s-a luat decizia de a mprejmui toate frag-mentele mpreun.

S se scrie un program care s determine lungimea minima plasei necesare pentru a ngrdi fragmentele zidului.

Date de intrarePrima linie a ierului de intrare conine dou numere:

n (1n180) numrul fragmentelor de zid; r (1r100) raza zidului. Urmeaz n perechi de numere ntregi, caredescriu fragmentele de zid: a

i, b

i msura unghiurilor

(n grade) care descriu nceputul i sfritul fragmentu-lui. Unghiurile se msoar ncepnd cu direcia nord dela centrul cetii, n sens opus micrii acelor de ceasornic(0 a

i; b

i< 360, a

i b

i). Fiecare fragment este descris

la fel mpotriva direciei de micare a acelor de ceasornic.

Fragmentele de zid nu au puncte comune.Date de ieire

Fiierul de ieire va conine lungimea minim a plaseinecesare, cu trei cifre dup virgul.Exemplu

cetate.in cetate.out

2 10 61.888

330 30

90 270


69/76

69


6.10. Druizi

Ruinele din Stonehenge se af-

l ntr-un loc special, unde seintersecteaz M linii energeticeale Pmntului. Liniile energe-tice mpart cmpia Stonehengen sectoare. n ecare an, n ceamai scurt zi a anului, N druizise adun n cmpie pentru unritual, ce asigur o road bogatpentru anul urmtor. Pentru succesul ritualului este necesarca n ecare sector al cmpiei, delimitat de liniile energetice,s se ae nu mai mult dect un druid. Cmpia are forma unuiptrat cu centrul n originea sistemului de coordonate i careare lungimea laturii 2L. Liniile energetice sunt linii drepte.Druizii sunt punctiformi i nu se pot aa pe liniile energetice.

S se scrie un program care determin dac exist sec-

toare ale cmpiei n care se a 2 sau mai muli druizi.Date de intrare

Fiierul de intrare conine cteva (cel mult 5) seturi dedate, separate prin cte o linie ce conine semnul #.

Prima linie a ecrui set de date conine numerele N, M iL (1 N 1000, 0 M 1000, 1 L 2000).

Urmeaz N linii ce conin cte dou numere ntregi xi, y

i

coordonatele druizilor. Toi druizii se a n interiorul cm-piei, oricare doi druizi nu coincid.Urmtoarele M linii ale setului de date conin cte un

triplet de numere ntregi ai, b

i, c

i. Numerele corespund

coecienilor ecuaiei Aix + B

iy + C

i= 0, care descrie linia

energetic i. Niciun druid nu se a pe o careva linie. Oricaredou linii nu coincid. Valorile a

i, b

i, c

inu depesc 10000

dup modul.


70/76


71/76

71


for i:=1 to m do

begin

readln(a,b,c);

if i=1 then begin l1a:=a; l1b:=b; l1c:=c; end;

if i=2 then begin l2a:=a; l2b:=b; l2c:=c; end;ae:=b*b+a*a;

be:=2*b*c;

ce:=c*c-a*a*2*r*r;

de:=be*be-4*ae*ce;

if a0 then begin

inc(n);

d[n].y:=(-be-sqrt(de))/2/ae;

d[n].x:=(-b*d[n].y-c)/a;

d[n].t:=D;

inc(n);

d[n].y:=(-be+sqrt(de))/2/ae;

d[n].x:=(-b*d[n].y-c)/a;

d[n].t:=D;

end

else begin

inc(n);

d[n].y:=-c/b;

d[n].x:=sqrt(2*r*r-c*c/b/b);

d[n].t:=D;inc(n);

d[n].y:=d[n-1].y;

d[n].x:=-d[n-1].x;

d[n].t:=D;

end;

end;

end; {readdata}

n rezolvare vor parcurse urmtoarele etape:

1. Toate liniile se intersecteaz ntr-un punct, care trebuiedeterminat. Dac numrul de linii este 0 sau 1, suntcteva cazuri elementare, care se cerceteaz aparte.Dac numrul de linii este mai mare sau egal cu doi,atunci se folosesc oricare dou linii pentru a determinacoordonatele punctului de intersecie.


72/76

72


2. Druizii se a n interiorulptratului cu latura 2L icentul n originea sistemu-

lui de coordonate. Ei se ai n interiorul cercului deraz 2L i centrul n ori-ginea sistemului de coordo-nate. Pentru ecare din lini-ile energetice se determinpunctele ei de intersecie cu

cercul de raz 2L i centrul n originea sistemuluide coordonate. Aceste puncte se marcheaz aparinnddreptelor (D) de separare a sectoarelor.

3. Originea sistemului decoordonate se deplaseaz npunctul de intersecie a drepte-lor (liniilor energetice). Apoi setrece la coordonatele polarepentru punctele ce reprezintdruizii i interseciile liniilorenergetice cu cercul (realizare

proceduramovecenter).

procedure movecenter;

begin

{se determin punctul de intersectie al dreptelor}

if l1a0 then

begin yint:=(l1c*l2a-l1a*l2c)/(l2b*l1a-l2a*l1b);

xint:=(-l1b*yint-l1c)/l1a;

end

else begin yint:=-l1c/l1b;

xint:=(-l2b*yint-l2c)/l2a;

end;


73/76

73


for i:=1 to n do

begin {se transfer originea..}

d[i].x:=d[i].x - xint; d[i].y:=d[i].y - yint;

{ ... si se determin coordonatele polare - unghiul!}

if d[i].x0 then

begin

d[i].a:=180/pi*arctan(abs(d[i].y/d[i].x));

if (d[i].x0) then d[i].a:=180-d[i].a;

if (d[i].x4))

then writeln(YES);

if (m=1) and(n=4) then

begin


74/76

74


{se determin pozitia druizilor fata de dreapta}

if sarrus(d[3],d[4],d[1])*sarrus(d[3],d[4],d[2]) < 0

then writeln(NO) else writeln(YES); end;

if m>=2 then

begin

{... si cazul general}

movecenter;

qsort(d,1,n);

vec:=FALSE;

for i:=1 to n-1 do

if (d[i].t=L) and(d[i+1].t=L)

then vec:=TRUE;

if vec then writeln(YES) else writeln(NO);

end;

end; {solve}


75/76

75


Notaii

1 2p p segment orientat (vector) cuoriginea n punctul p

1

1{ ,..., }NS p p= mulimea S, cu elementelep1, ..., pN

|S| cardinalul mulimii S

i incrementarea valorii i cu 1

k m variabilei ki se atribuie valoareavariabilei m

[a, b] interval cu extremitile a, b

abc triunghi cu vrfurile a, b, c

DV(S) diagrama Voronoi pentru mulimea S

T(S) triangularizarea mulimii S

Q(S) nfurtoarea convex a mulimii S

A B dinA rezultB

A B A este echivalent cuB

, ( )x X x X x aparine (nu aparine) mulimiiX

{ }: x X Q submulimea elementelorx dinX, care

satisfac condiia QA B A se conine nB (A este submulime

a mulimiiB)

qsort(A,n) apel al procedurii pentru sortareastructurii de dateAdin n elemente


76/76


Bibliograe

1. Ammeraal, Leen.Programming Principles in ComputerGraphics. John Wiley and Sons, 1986.

2. Ammeraal, Leen. Computer Graphics for the IBM PC. JohnWiley and Sons, 1986.

3. Cerchez, Emanuela.Programarea n limbajul C/C++ pen-tru liceu. Vol III. Iai: Polirom, 2007.

4. Cormen, Thomas. Introducere n algoritmi. Cluj: Agora.

5. Foley, James; Andries, Van Dam. Fundamentals of Interac-tive Computer Graphics. Addison-Wesley Publishing, 1984.

6. Giumale, Cristian. Introducere n analiza algoritmilor. Iai:Polirom, 2004.

7. Sedgewick, Th.Algorithms in C. Addison Wesley, 2001.

8. Williamson, Gill. Combinatorics for Computer Science. NewYork: Dover publications, 2002.

9. , . ++. : , 1997.

10. , . . : ,1986.

11. , . . . : , 2001.

12. , . .

algoritmi şi probleme geometrie computationala

Documents