F005B. Nines russes P96460

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 \ge 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.