Põranda katmine

시간 제한1초메모리 제한1024 MB

요약
두 직사각형 판을 자르지 않고 겹쳐도 되게 배치해 X x Y 방을 덮는 좌표를 찾거나 EI SAA를 출력한다.
난이도

보통10점 중 6점

유형
기하, 구현, 완전 탐색, 그리디
정답자
아직 제출이 없습니다

문제

Maaler Mati hakkab toa lage värvima ja tal on vaja põrand kinni katta, et värvitilgad seda ära ei määriks. Põranda katmiseks on tal kaks papptahvlit. Aga neid tahvleid on hiljem veel tarvis ja Mati ei taha neid lõigata ega kokku murda. Kui põranda saab katta ühe tahvliga, siis Mati teist tahvlit ei kasuta. Nii tuba kui tahvlid on ristküliku kujuga. Toa mõõtmed on X×YX \times Y cm, esimese tahvli mõõtmed A_1×B_1A\_1 \times B\_1 cm ja teise omad A_2×B_2A\_2 \times B\_2 cm.

Kontrollida, kas nende tahvlitega saab katta korraga kogu põranda. Tahvleid võib pöörata ja nad võivad ka osaliselt üksteist katta, aga ei saa ulatuda üle põranda ääre. Kui põranda katmine on võimalik, siis leida sobiv tahvlite paigutus XY-teljestikus, kus toa vastasnurkade koordinaadid on (0,0)(0, 0) ja (X,Y)(X, Y). Kui lahendeid on mitu, siis esitada üks neist.

입력

Sisendi esimesel real on tühikuga eraldatud täisarvud XX ja YY: toa mõõtmed (0<X,Y≤5000 < X, Y \le 500). Teisel real on ühe tahvli mõõtmed A_1A\_1 ja B_1B\_1 ning kolmandal real teise tahvli mõõtmed A_2A\_2 ja B_2B\_2 samas vormingus (0<A_1,B_1,A_2,B_2≤5000 < A\_1, B\_1, A\_2, B\_2 \le 500).

출력

Kui põrandat ei saa nõutud viisil katta, kirjutada väljundi ainsale reale 'EI SAA'.

Kui programmi leitud lahend kasutab kahte tahvlit, siis kirjutada väljundi kahele reale kummalegi neli tühikutega eraldatud täisarvu. Esimesel real kirjeldada esimese tahvli asendit, andes koordinaattasandi suhtes vasakpoolse alumise nurga koordinaadid X_1,1X\_{1,1} ja Y_1,1Y\_{1,1} ning parempoolse ülemise nurga koordinaadid X_1,2X\_{1,2} ja Y_1,2Y\_{1,2}. Teisel real anda teise tahvli nurkade koordinaadid X_2,1X\_{2,1} ja Y_2,1Y\_{2,1} ning X_2,2X\_{2,2} ja Y_2,2Y\_{2,2}.

Kui lahend kasutab ainult esimest tahvlit, siis kirjutada väljundi esimesele reale selle nurkade koordinaadid ja teisele reale sümbol 'Z'. Kui lahend kasutab ainult teist tahvlit, siis kirjutada väljundi esimesele reale sümbol 'Z' ja teisele reale teise tahvli asendi kirjeldus.

예제3

  1. 예제 1

    입력
    500 200
    200 300
    250 200
    
    예상 출력
    0 0 300 200
    250 0 500 200
    
  2. 예제 2

    입력
    400 300
    200 400
    300 400
    
    예상 출력
    Z
    0 0 400 300
    
  3. 예제 3

    입력
    300 400
    400 100
    300 300
    
    예상 출력
    EI SAA