Fişierul intrare/ieşire:colaj.in, colaj.outSursăOJI 2008, clasa a 10-a
AutorCarmen MincaAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.05 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Colaj

La etapa finala a Concursului pe Echipe al Micilor Artisti, pe primul loc s-au clasat doua echipe A si B, cu acelasi punctaj. Comisia de Evaluare, pentru a le departaja, a introdus o noua proba de baraj care vizeaza atat talentul copiilor, cat si istetimea lor.

Astfel, echipa A trebuie sa realizeze un colaj alb-negru avand la dispozitie o plansa dreptunghiulara de culoare alba si N dreptunghiuri de culoare neagra. Membrii acestei echipe vor trebui sa lipeasca pe plansa toate dreptunghiurile, cu laturile paralele cu laturile plansei. Pot exista si dreptunghiuri lipite in interiorul altui dreptunghi, sau dreptunghiuri care se intersecteaza, sau dreptunghiuri cu laturi pe laturile plansei, precum si suprafete din plansa neacoperite cu dreptunghiuri.

Dupa ce aseaza toate dreptunghiurile, membrii echipei A trebuie sa comunice echipei B numarul N de dreptunghiuri negre primite, lungimea m a laturii orizontale a plansei, lungimea p a laturii verticale a plansei, si coordonatele varfurilor din stanga-jos si dreapta-sus ale fiecarui dreptunghi de pe plansa (coordonate referitoare la reperul cartezian xOy cu originea O in coltul din stanga-jos a plansei si cu axa de coordonate Ox, respectiv Oy, pe dreapta suport a laturii orizontale, respectiv a laturii verticale a plansei).

Pentru a castiga concursul, echipa B trebuie sa ghiceasca numarul zonelor continue maximale de culoare alba, continute de colajul realizat de echipa A. O zona alba este considerata continua daca oricare ar fi doua puncte P, Q din zona respectiva, se poate uni punctul P de punctul Q printr-o linie dreapta sau franta care sa nu intersecteze interiorul nici unui dreptunghi negru. O zona alba continua este considerata maximala daca nu exista o alta zona alba continua de arie mai mare care sa includa zona respectiva.

Cerinta

Scrieti un program care sa citeasca numarul N al dreptunghiurilor negre primite de echipa A, lungimile m si p ale laturilor plansei, coordonatele varfurilor din stanga-jos si dreapta-sus ale fiecarui dreptunghi negru primit, si care sa determine numarul zonelor continue maximale de culoare alba existente in colajul realizat de echipa A.

Date de intrare 

Fisierul de intrare colaj.in va contine:

  • Pe prima linie, o valoare naturala N, reprezentand numarul de dreptunghiuri negre date echipei A.
  • Pe a doua linie, 2 numere naturale m si p, separate prin spatiu, reprezentand lungimile laturilor plansei
  • Urmatoarele N linii contin cate patru numere naturale, separate prin cate un spatiu, care reprezinta coordonatele (a1,b1) si (c1,d1) ale varfurilor din stanga-jos si dreapta-sus ale primului dreptunghi, ..., coordonatele(aN,bN) si (cN,dN) ale varfurilor din stanga-jos si dreapta-sus ale celui de-al N-lea dreptunghi.

Date de iesire

In fisierul de iesire colaj.out va contine o singura linie pe care se va scrie un singur numar natural reprezentand numarul zonelor continue maximale de culoare alba, continute de colaj.

Restrictii

  • 1 ≤ N ≤ 100, a1 < c1 ≤ m, a2 < c2 ≤ m,..., aN < cN ≤ m, b1 < d1 ≤ p, b2 < d2 ≤ p,..., bN < dN ≤ p
  • Toate coordonatele varfurilor dreptunghiurilor si lungimile laturilor plansei sunt numere naturale, 0 < m, p < 8000
  • Daca (x,y) si (z,t) sunt coordonatele a doua varfuri din doua dreptunghiuri distincte, atunci: x ≠ z si y ≠ t.
  • In 40% din teste: N < 30, m ≤ 180, p ≤ 180;
  • In alte 40% din teste: 70 ≤ N ≤ 100, 180 < p < 1000, 180 < m < 1000;
  • In celelalte 20% din teste: 50 < N < 80, 7000 < m < 8000, 7000 < p < 8000.

Exemplu

colaj.incolaj.out
7
17 16
1 1 10 5
2 6 8 8
0 9 17 15
3 2 4 11
5 3 6 12
7 4 12 13
14 10 16 14
6

Explicatie

Sunt 7 dreptunghiuri negre. Colajul realizat de echipa A este cel din desenul de mai sus. Se observa 6 zone continue maximale de culoare alba continute de colaj (cele numerotate in figura).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content