Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Colaj

Adăugată de :
sorynsoo
Sursă :
OJI2008
Autor :
-
Grupă :
Medie
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
200 ms
Limită memorie :
4096 kbytes

La etapa finală a Concursului pe Echipe al Micilor Artişti, pe primul loc s-au clasat două echipe A şi B, cu acelaşi punctaj. Comisia de Evaluare, pentru a le departaja, a introdus o nouă probă de baraj care vizează atât talentul copiilor, cât şi isteţimea lor.

Astfel, echipa A trebuie să realizeze un colaj alb-negru având la dispoziţie o planşă dreptunghiulară de culoare albă şi n dreptunghiuri de culoare neagră. Membrii acestei echipe vor trebui să lipească pe planşă toate dreptunghiurile, cu laturile paralele cu laturile planşei. Pot exista şi dreptunghiuri lipite în interiorul altui dreptunghi, sau dreptunghiuri care se intersectează, sau dreptunghiuri cu laturi pe laturile planşei, precum şi suprafeţe din planşă neacoperite cu dreptunghiuri.

După ce aşează toate dreptunghiurile, membrii echipei A trebuie să comunice echipei B numărul n de dreptunghiuri negre primite, lungimea m a laturii orizontale a planşei, lungimea p a laturii verticale a planşei, şi coordonatele vârfurilor din stânga-jos şi dreapta-sus ale fiecărui dreptunghi de pe planşă (coordonate referitoare la reperul cartezian xOy cu originea O în colţul din stânga-jos a planşei şi cu axa de coordonate Ox, respectiv Oy, pe dreapta suport a laturii orizontale, respectiv a laturii verticale a planşei).

Pentru a câştiga concursul, echipa B trebuie să ghicească numărul zonelor continue maximale de culoare albă, conţinute de colajul realizat de echipa A. O zonă albă este considerată continuă dacă oricare ar fi două puncte P, Q din zona respectivă, se poate uni punctul P de punctul Q printr-o linie dreaptă sau frântă care să nu intersecteze interiorul nici unui dreptunghi negru. O zonă albă continuă este considerată maximală dacă nu există o altă zonă albă continuă de arie mai mare care să includă zona respectivă.

 

Cerinţă

Scrieţi un program care să citească numărul n al dreptunghiurilor negre primite de echipa A, lungimile m şi p ale laturilor planşei, coordonatele vârfurilor din stânga-jos şi dreapta-sus ale fiecărui dreptunghi negru primit, şi care să determine numărul zonelor continue maximale de culoare albă  existente în colajul realizat de echipa A.

 

Date de intrare

Fişierul de intrare colaj.in conţine:

n

m p

a1 b1 c1 d1

...

an bn cn dn

  • pe prima linie, o valoare naturală n, reprezentând numărul de dreptunghiuri negre date echipei A
  • pe a doua linie, 2 numere naturale, separate prin spaţiu, reprezentând lungimile laturilor planşei
  • următoarele n linii conţin câte patru numere naturale, separate prin câte un spaţiu, care reprezintă coordonatele (a1,b1) şi (c1,d1) ale vârfurilor din stânga-jos şi dreapta-sus ale primului dreptunghi,..., coordonatele(an,bn) şi (cn,dn) ale vârfurilor din stânga-jos şi dreapta-sus ale celui de-al n-lea dreptunghi.

 

Date de ieşire

Fişierul de ieşire colaj.out va conţine o singură linie pe care se va scrie un singur număr natural reprezentând numărul zonelor continue maximale de culoare albă, conţinute de colaj.

 

Restricţii şi precizări

  • 1 <= n <= 100, a1 < c1 £ m, a2 < c2 <= m,..., an < cn <= m,  b1 < d1 <= p, b2< d2 <= p,..., bn < dn <= p
  • Toate coordonatele vârfurilor dreptunghiurilor şi lungimile laturilor planşei sunt numere naturale, 0
  • Dacă (x,y) şi (z,t) sunt coordonatele a două vârfuri din două dreptunghiuri distincte, atunci: x¹z şi y¹t.
  • În 40% din teste:  n < 30,  m <= 180,  p <= 180; în 40% din teste: 70 <= n <= 100, 180 < p < 1000,  180 < m < 1000;  în 20% din teste: 50 < n < 80,  7000 < m < 8000, 7000 < p < 8000

 

Exemplu

  Date de intrare

  Date de iesire

  Explicaţie

  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 

  n=7, m=17, p=16.

  Sunt 7 dreptunghiuri negre.

  Colajul realizat de echipa A este cel din     desenul alăturat. Se observă 6 zone continue   maximale de culoare albă conţinute de colaj   (cele numerotate în figura alăturată).


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Nu există indicații de rezolvare



Comentarii

Adauga un comentariu: Click !