Lista de probleme 6

Se dă un număr n și n triplete de forma l, c, h, reprezentând lungimea egala a doi stâlpi, lungimea cablului dintre acestea și înălțimea la care atârnă cablul față de podea.

Se cere să se afle distanța dintre fiecare doi stâlpi.

Păcală a primit, aşa cum era învoiala, un petec de teren de pe moşia boierului. Terenul este împrejmuit complet cu segmente drepte de gard ce se sprijină la ambele capete de câte un par zdravăn. La o nouă prinsoare, Păcală iese iar in câştig şi primeşte dreptul să strămute nişte pari, unul câte unul, cum i-o fi voia, astfel încât să-şi extindă suprafaţa de teren. Dar învoiala prevede că fiecare par poate fi mutat în orice direcţie, dar nu pe o distanţă mai mare decât o valoare dată (scrisă pe fiecare par) şi fiecare segment de gard, fiind cam şubred, poate fi rotit şi prelungit de la un singur capăt, celălalt rămânând nemişcat.

Cunoscând poziţiile iniţiale ale parilor şi valoarea înscrisă pe fiecare par, se cere suprafaţa maximă cu care poate să-şi extindă Păcală proprietatea. Se ştie că parii sunt daţi într-o ordine oarecare, poziţiile lor iniţiale sunt date prin numere întregi de cel mult 3 cifre, distanțele pe care fiecare par poate fi deplasat sunt numere naturale strict pozitive şi figura formată de terenul iniţial este un poligon neconcav.

Fie A o mulțime de N puncte Ai în plan de coordonate întregi cunoscute (Ai.x, Ai.y). Pentru o întrebare definită printr-un punct Q=(Q.x, Q.y) se cere aria înfășurătorii convexe a punctelor: {Q} ∪ {Ai | Ai.x < Q.x și Ai ∈ A }.

Înfășurătoarea convexă a unei mulțimi de puncte este poligonul convex de arie minimă care conține toate punctele în interior sau pe laturile acestuia.

Determinați răspunsurile pentru M întrebări de tipul enunţat mai sus, relativ la mulțimea inițială A.

Ion și Gheorghe au primit moștenire două parcele de pământ de formă poligonală. Într-o zi, Ion l-a văzut pe Gheorghe că a folosit o parte din bucata lui. Certându-se, aceștia au remarcat că acea bucată era parte din moștenirea amândurora. Au hotărât să se ducă la judecată și să se rezolve eroarea care a făcut ca parcelele moștenite să se intersecteze. Dar cum procesul va începe destul de târziu, au hotărât să nu folosească acea bucată comună până nu va fi rezolvată problema.

Vasile este un tânăr programator angajat recent la o firma oarecare din domenul IT. Deoarece câştigă foarte bine el şi-a achiziţionat un teren de formă dreptunghiulară. Colţurile dreptunghiului care definesc acest teren au coordonatele (0,0), (N,M), unde N şi M sunt numere naturale.

Pe acest teren Vasile doreşte să construiască în primul rând o piscină de arie maximă, de formă dreptunghiulară, cu laturile respectiv paralele cu cele ale terenului.

Deşi credea că şi-a îndeplinit visul, Vasile şi-a dat seama că în viaţă nimic nu este atât de uşor deoarece au apărut două restricţii pe care el trebuie să le respecte:

• Deoarece alimentarea cu apă se poate face doar în colţurile dreptunghiului care reprezintă terenul, piscina trebuie să aibă un punct comun cu unul dintre punctele (0,0),(0,M),(N,0) sau (N,M).
• Pe teren se află P pomi la coordonate întregi cunoscute. Aceştia nu pot face parte din dreptunghiul ce defineşte piscina. Iar Vasile nici nu se gândeşte să taie vreun copac pentru că îi place aerul curat. Copacii se pot afla însă pe marginea piscinei.

Scrieţi un program care determină aria maximă pe care o poate avea piscina respectând restricţiile din enunţ.

Se dau N puncte din plan prin coordonatele lor.
Se mai dau Q perechi de puncte, diferite de cele date inițial.

Să se verifice, pentru fiecare pereche de puncte (A , B) dintre cele Q, dacă există traseu care pornește din A și ajunge în B, prin deplasări cu pași de lungime 1 spre Nord, Vest, Sud, Est și evitând orice punct dintre cele N date inițial.