F005B. Nines russes P96460

[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:

(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ó

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.