만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

바닥 덮기

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

요약
바닥 크기 X×Y와 회전할 수 있는 직사각형 천 두 장이 주어질 때, 천을 자르거나 접지 않고 바닥을 덮는 배치를 찾습니다. 덮을 수 없으면 'EI SAA'를 출력합니다.
난이도

보통10점 중 6점

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

문제

마티는 방의 천장을 칠하려고 한다. 페인트 방울이 바닥에 튀지 않도록 바닥을 덮어야 하는데, 이를 위해 판지 두 장이 있다. 하지만 판지는 나중에도 필요하므로 자르거나 접으면 안 된다. 판지 한 장으로 바닥 전체를 덮을 수 있다면 나머지 판지는 쓰지 않는다.

방과 판지는 모두 직사각형이다. 방의 크기는 X×YX \times Y cm이고, 첫 번째 판지의 크기는 A1×B1A_1 \times B_1 cm, 두 번째 판지의 크기는 A2×B2A_2 \times B_2 cm이다.

두 판지로 바닥 전체를 한 번에 덮을 수 있는지 확인하라. 판지는 회전해도 되고 서로 일부가 겹쳐도 된다. 다만 판지가 방의 가장자리 밖으로 나가면 안 된다. 덮는 것이 가능하면 XY 좌표계에서 판지의 위치를 구하라. 이때 방의 대각선 꼭짓점은 (0,0)(0, 0)과 (X,Y)(X, Y)이다. 가능한 배치가 여럿이면 그중 하나를 출력한다.

입력

첫 줄에 방의 크기 XX와 YY가 공백으로 구분된 정수로 주어진다 (0<X,Y≤5000 < X, Y \le 500). 둘째 줄에는 첫 번째 판지의 크기 A1A_1과 B1B_1이, 셋째 줄에는 두 번째 판지의 크기 A2A_2와 B2B_2가 같은 형식으로 주어진다 (0<A1,B1,A2,B2≤5000 < A_1, B_1, A_2, B_2 \le 500).

출력

바닥을 덮을 수 없으면 한 줄에 'EI SAA'를 출력한다.

두 판지를 사용하면 각 줄에 네 정수를 출력한다. 첫 줄에는 첫 번째 판지의 왼쪽 아래 꼭짓점 좌표 X1,1X_{1,1}, Y1,1Y_{1,1}과 오른쪽 위 꼭짓점 좌표 X1,2X_{1,2}, Y1,2Y_{1,2}를 쓴다. 둘째 줄에는 두 번째 판지의 꼭짓점 좌표 X2,1X_{2,1}, Y2,1Y_{2,1}, X2,2X_{2,2}, Y2,2Y_{2,2}를 쓴다.

첫 번째 판지만 사용하면 첫 줄에 그 꼭짓점 좌표를 쓰고 둘째 줄에 'Z'를 쓴다. 두 번째 판지만 사용하면 첫 줄에 'Z'를 쓰고 둘째 줄에 두 번째 판지의 꼭짓점 좌표를 쓴다.

예제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