F005B. Nines russes P96460


Statement
 

pdf   zip

html

[r] Les nines russes són un souvenir rus consistent en una successió de nines, de mides decreixents, cadascuna (excepte la primera) dintre de l’anterior.

Feu un programa que, per a cada conjunt de rectangles donat, decideixi si són com nines russes, és a dir, si per a cada parell de rectangles, un d’ells està dins de l’altre.

Els tres primers exemples d’entrada es corresponen a les figures següents. Només la de l’esquerra és una nina russa.

Per resoldre aquest problema, useu la definició següent d’un rectangle:

struct Rectangle { int est, oest, nord, sud; };

(Per exemple, el rectangle de més a la dreta de dalt té els valors respectius 25, 21, 9 i 2.)

Usant aquesta definició, implementeu i useu la funció

bool esta_inclos(const Rectangle& a, const Rectangle& b);

la qual indica si el rectangle a està inclòs estrictament (és a dir, sense igualtat en cap de les coordenades) dins del rectangle b o no.

Entrada

L’entrada consisteix en una seqüència de casos separats amb una línia en blanc. Cada cas comença amb un natural n ≥ 1, seguit de n rectangles amb els costats paral·lels als eixos horitzontal i vertical. Cada rectangle es defineix amb quatre coordenades enteres: est, oest, nord i sud. Dintre de cada cas no hi haurà coordenades horitzontals o verticals repetides.

Sortida

Per a cada cas, si són nines russes, cal escriure els rectangles de gran a petit. Altrament, cal escriure "no son nines russes". Separeu la sortida dels casos amb una línia en blanc.

Observació

El vostre programa ha de ser eficient. En particular, les solucions quadràtiques en n seran rebutjades, ja sigui directament pel Jutge o en la posterior correcció manual.





Public test cases
  • Input

    3
    8 1 9 1
    5 3 6 5
    6 2 7 4
    
    4
    19 10 8 1
    16 15 5 4
    12 11 6 2
    18 13 7 3
    
    2
    24 23 9 2
    25 21 5 3
    
    1
    8 -100 0 -100
    
    2
    3 2 1 0
    102 100 3 2
    

    Output

    8 1 9 1
    6 2 7 4
    5 3 6 5
    
    no son nines russes
    
    no son nines russes
    
    8 -100 0 -100
    
    no son nines russes
    
  • Information
    Author
    Professorat de P1
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++