Lista de probleme 5

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#2552 Poz C++

Să se scrie definiția unei funcții C++ care primește ca argumente informații despre două dreptunghiuri cu laturile paralele cu axele de coordonate și stabilește dacă cel două dreptunghiuri sunt identice, sunt interioare unul altuia, sunt exterioare sau se suprapun parțial.

#2610 Discuri

Se dau N numere reale considerate ca fiind razele a N discuri. Considerăm că așezăm un disc în sistemul xOy dacă îl plasăm la o coordonată x pozitivă suficient de mare, tangent cu axa Ox și deasupra ei, apoi îl împingem spre Oy până când devine tangent cu Oy sau cu primul disc așezat anterior întâlnit. În figura rezultată după așezarea tuturor discurilor în ordinea dată unele dintre ele pot fi considerate dispensabile, pentru că prin eliminarea lor nu se modifică lățimea totală a figurii, adică nici un disc nu se mai poate deplasa spre stânga. Identificați toate discurile dispensabile din figură.

#2387 mosia1

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.

Arhipelagul Zopopan este format din n insule de formă triunghiulară numerotate de la 1 la n. Fiecare insulă este localizată prin coordonatele carteziene ale vârfurilor.

Administrația dorește să cumpere elicoptere pentru a realiza transportul între insule. Un elicopter va putea să asigure o rută între două insule pe distanța minimă obținută pe orizontală sau verticală (paralel cu axele de coordonate). În plus, datorită capacității rezervorului o astfel de rută nu poate să depășească o valoare k – număr natural. Elicopterele parcurg rutele în ambele sensuri.
Investiția trebuie să îndeplinească următoarele condiții:

  1. Numărul de elicoptere cumpărate să fie minim.
  2. Numărul de perechi de insule între care se poate realiza transportul, folosind unul sau mai multe elicoptere să fie maxim.
  3. Suma lungimii tuturor rutelor să fie minimă.

Să se scrie un program care pentru n, k şi coordonatele vârfurilor insulelor cunoscute, determină:

  1. numărul minim de elicoptere ce vor fi cumpărate de administraţie;
  2. numărul perechilor neordonate de insule între care se poate realiza transportul prin elicoptere direct sau indirect;
  3. suma distantelor parcurse de toate elicopterele cumpărate (distanța parcursă de un elicopter se consideră distanța dintre insulele între care acesta asigură transportul).

#3004 Links

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.