8/19/2019 Schite de Solutii

1/8

8/19/2019 Schite de Solutii

2/8

> 5. ** Se dau 2 poligoane convexe fiecare avand> maxim 1000 de> varfuri. Se cere sa se determine intersectia lor> (bursele agora,i-am> dat 2 stele desi la concurs am complicat-o rau de> tot).

Se poate verifica ce puncte din primul poligon suntinterioare celui de al doilea si dupaia ce puncte dinal 2-lea poligon fac parte din primul si sa se adaugela multimea asta de puncte punctele de intersectie alelaturilor celor 2-a poligoane. Acuma mai ramane defacut algoritmul de infasuratoare convexa pt puncteleastea. Complexitate O(n^2). Exista un algoritm desteptin O(n), da nu cred ca se merita sa fie invatat ptconcurs.

> 6. *** Se dau n puncte (n perechea de> puncte din cele n cu distanta maxima intre ele> (parca am vazut-o pe> la ceva acm, s-ar putea sa fie si in cormen, medie +> * daca nu stiti> cum sa o faceti, implemenatrea e *).

Evident perechea de puncte la distanta maxima seafla pe marginile infasuratorii convexe. Daca punctelenu sunt bine alese (adica random) o sa fie putinepuncte pe conturul infasuratoarei convexe deci aici armerge bruteforce O(h^2) unde h e numarul de puncte depe infasuratoarea convexa.Exista 2 algoritmi mai buni O(h log h) si O(h).Primul : pt fiecare punct se cauta cu cautare binaraal 2-lea punct.Al doilea: se foloseste o tehnica asemanatoare cuaceea care s-a folosit la problema cu triunghiuldreptunghic. Avem 2 indici i1,i2 de puncte de pe

infasuratoarea convexa. cat timp distanta dintre i1 sii2 e mai mica decat aceea dintre i1 si i2+1 seincrementeaza i2. Se actualizeaza la fiecare pasdistanta maxima. Se incrementeaza i1. Asta se facepana cand i1 ajunge sa fie a 2-a oara primul punct.Evident acest algoritm are complexitatea O(h).

> 6 b *** Se dau n puncte (n perechea de> puncte din cele n cu distanta minima intre ele.> (cormen si bursele> agora)

....

> 7. * Se dau n puncte (n necoliniare. Gasiti un romb> cu varfurile in punctele date, (daca exista) (s-a> propus pe lista de> discutii [olimpiada] acum vreo 2 ani).

O(n^3 log n), O(n^3): Se iau oricare 3 puncte siacest triunghi daca e isoscel se poate completa

8/19/2019 Schite de Solutii

3/8

intr-un singur fel ca sa devina romb, daca eechilateral se poate compleat in 3 moduri si punctelelipsa se cauta prin cautare binara intre punctelesortate O(log n), sau se cauta intr-o tabela dedispersie (hash table) in O(1).

O(n^2 log n), O(n^2): Amintesc proprietatea ca laromb diagonalele sunt perpendiculare si seinjumatatesc. Se iau toate perechile de puncte, sedetermina mijloacele segmentelor si panta lor si sesorteaza sau se bvaga intr-o tabela de dispersie.Dupaia pt fiecare mijloc si panta se cauta daca existain structura de date (sir ordonat sau hashtable)acelasi punct cu panta perpendiculara. Daca oricecautare are succes inseamna ca am gasit un romb.

> 8. Se dau n puncte (n minima care> contine in interior sau pe frontiera cel putin> jumatate din punctele> date (internet problem solving contest 2002, astia> au probleme faine> de tot).

Aici am uitat ca axele patratului trebuiau sa fieparalele cu axele de coordonate.

O(n^2 log n) timp, O(n^2) memorie: Se obtine listaordonata a x-lor si lista ordonata a y-lor. Acuma sefoloseste o matrice unde a[i][j] inseamna ca exista unpunct in multime de coordonate x[i],y[j]. Pentru olungime data se poate verifica in O(n^2) daca existapatrat cu dimensiunea asta care sa contina jumatatedin puncte. Si cu o cautare binara e gata problema.Numarul de dimensiuni diferite e de ordinul lui n^2(adica diferentele dintre xi,xj si yi,yj) care se potordona si folosi in cautarea binara a lungimiioptime

de latura.

Pe siteul de la ipsc este o rezolvare in O(n^2 log^2n). Cred ca si rezolvarea de mai sus poate fiimbunatatita ca sa nu se foloseasca chestia cudistantele de la sfarsit.

> 9. ***** Se dau n puncte in plan (n coordonate intregi> mai mici> in modul ca 250, oricare 3 necoliniare. Gasiti un> triunghi cu> varfurile in punctele date de perimetru minim. (Nu

> stiu o rezolvare> simpla la problema cu restrictie 250, dar cred ca> pot face o> rezolvare un pic mai complicata pentru coordonate> reale.) (lista> [olimpiada])

La vremea respectiva cand s-a discutat problema sevorbea despre o cautare locala a cate trei puncte.Tehnicii ii zice bucketing si este foarte folositoare

8/19/2019 Schite de Solutii

4/8

8/19/2019 Schite de Solutii

5/8

decrementeaza nr de puncte din centrul curent.

> 14. *** Se dau n dreptunghiuri cu laturile paralele> cu axele de> coordonate ce se pot suprapune(n aria figurii> acoperite de aceste dreptunghiuri. (IOI 98, selectie> lot acm> Universitatea Bucuresti)

Se poate face o matrice cu dimensiuni 2n*2n. un felde matrice redusa in care a[i][j] inseamna dacadreptunghiul (x[i],x[i+1])*(y[j],y[j+1]) este ocupatsau nu (unde x e sirul tuturor coordonatelor xsortate, y la fel).Sau se poate face analiza fiecare banda de y[i]y[i+1]si determina in O(n) aria ocupata dee pe banda asta,daca se sorteaza dreptunghiurile in ordinea x-lor.Se poate face si in O(n log n) cu arbori de intervale(cormen).

> 15. *** Se dau n triunghiuri dreptunghice isoscele> cu laturile> perpendiculare paralele cu axele de coordonate

> (n aria reuniunii triunghiurilor. (BOI 2002)

Se ordoneaza punctele pe x si se face o scanare, dinaproape in aproape se trateaza fiecare banda pe y. Dela x[i] la x[i+1].

> 16. Se da un numar natural n. Care este numarul de> regiuni in care> se imparte planul de n cercuri care nu se> intersecteaza cate 3 intr-> un punct si oricare 2 se intersecteaza in 2 puncte (> :) problema de

> pe UVA).

Prin inductie se determina numarul de regiuni. Dacapt n avem X(n) regiuni, cand se adauga al n+1 lea cercacesta se intersecteaza cu cele n cercuri in 2npuncte. Deci o sa fie n regiuni impartite in 2 decercu asta, deci se adauga n regiuni noi. Recurenta eX(n+1)= X(n)+n sau ceva de genu asta.

> 17. *** Care este numarul maxim de regiuni in care> se inparte> planul daca folosim n drepte. Aceeiasi problema> pentru cercuri.

> Aceeiasi problema pentru spatiu si sfere (problema> data la bursele> agora) (Probleme neelementare tratate elementar> Iaglom,Iaglom).

Se foloseste ideea de mai sus.

> 18. * Avem n drepte in plan fiecare dreapta fiind> data prin 2> perechi de coordonate (n

8/19/2019 Schite de Solutii

6/8

> cate zone se> imparte astfel planul (internet problem solving> contest 2001).

Aceeiasi idee de mai sus. Se vede la fiecare pascate drepte intersecteaza o dreapta si asa se vedecate regiuni noi se adauga la cele vechi.

> 19. ** (problema de-a mea :)) Se dau n de puncte de> coordonate> intregi (n cu varfurile in> punctele astea au ca arie un numar intreg.

Dupa cum stiti aria unui triunghi e abs(1/2*det(x1,y1,1,x2,y2,1,x3,y3,1)) deci daca aria unuitriunghi e intreaga daca determinantul e par.Paritatea determinantului e data de paritatilecoordonatelor. Acuma clasificam coordonatele in 4clase: (x par, y par),(x impar, y par)(x impar, yimpar)(x par, y impar). Si ce mai ramane de facut e saverificam ce triplete de clase dau determinant par.

> 20. * Sa se determine aria unui poligon oarecare ce

> are n varfuri> (n 21. Sa se determine daca un poligon cu n varfuri> (n convex.

Daca fiecare triunghi de 3 puncte consecutive de pemarginea poligonului are acelasi semn atunci poligonul

e convex.

> 22. Sa se determine daca un poligon are varfurile> date in sens> trigonometric sau sens orar (n23. Sa se determine centrul de greutate al unui>poligon oarecare ce>are n varfuri (nregion, olimpiada>online)http://www.faqs.org/faqs/graphics/algorithms-faq/

8/19/2019 Schite de Solutii

7/8

Tot acolo, se bazeaza pe formula ariei.

>24. Se dau n segmente (ndreapta ce>intersecteaza numarul maxim posibil de segmente.>(lista [olimpiada])

Orice dreapta ce intersecteaza numarul maxim desegmente poate fi translatata astfel incat saintersecteze acelasi numar de segmente dar sa aiba peea o extremitate de segment, dupaia poate fi rotita saaiba inca o extremitate pe ea. Deci complexitateO(n^3).

Se poate si in O(n^2 log n) cu ideea de sortare injurul punctului.

>25. Se dau doua multimi de n si m puncte (n,mSa se determine o dreapta care separa aceste doua>multimi. (baraj 98)

O dreapta de separare se poate translata pana candintalneste un varf al unui poligon. Acuma pt fiecarepunct se testeaza daca punctele din celalalt poligon

sunt in acelasi semiplan. Asta se face determinandunghiul cu fiecare pct din celalalt poligon si se vededaca diferenta intre cel mai mic si cel mai mare punctca unghi e 26. * Se da un poligon oarecare cu n varfuri>(npoligonului. (pregatire lot 99)

http://www.faqs.org/faqs/graphics/algorithms-faq/

>27. *** Se da un poligon convex cu n varfuri>(npuncte (mpuncte sunt interioare poligonului. (balcaniada 99,>cu date ca si la problema anterioara)

Se considera un vf al poligonului si fasciculeledeterminate de punctu asta si cate 2 semidrepte cepleaca din el inspre cate 2 puncte consecutive de pepoligon. Cu cautare binara se gaseste fascicolul incare e fiecare punct si acuma mai ramane de verificatdaca punctul respectiv e interior triunghiului.

>28. *** Se da un poligon convex de n noduri>(n(mpoligonul. (baraj 98, ceoi 2002)

tot cautare binara

>29. * Se dau n puncte de coordonate intregi in plan,

8/19/2019 Schite de Solutii

8/8

>sa se determine numarul de puncte de coordonate>intregi de pe contrulul poligonului, aria>poligonului, si numarul de puncte de coordonate>intregi interioare poligonului. (selectie acm Babes>2003 :))

Parca ii zice formula lui pick la chestia ce amfolosit-o in concurs se gaseste in Problemeneelementare tratate elementar (Iaglom, Iaglom).

Pt determinarea numarului de puncte de coordonateintregio pe un segment cu capetele de coordonateintregi se foloseste algoritmul lui Euclid.

>30. *** Se da un poligon convex cu n varfuri>(nse determine numarul de puncte de coordonate intregi>din interiorul poligonului. (eu am vazut-o pe>lista lui Francu, dar cred ca e si pe acm.timus.ru)

O(n)

>31. *** Se dau n puncte (nSa se determine dreptunghiul de arie maxima continut

>in dreptunghiul initial cu laturile paralele cu cele>ale dreptunghiului initial, care nu contine nici un>punct in interior. (El Judge, UVA, CEOI 96>sau 97)O(n^2) poate va explica csibi sau adi.

O sa mai lucrez la mailu asta sa le redactez maibine. Daca aveti idei noi sau corecturi var rogtrimiteti-mi.

Salut,Cosmin