바닥 덮기
시간 제한1초메모리 제한1024 MB
바닥 크기 X×Y와 회전할 수 있는 직사각형 천 두 장이 주어질 때, 천을 자르거나 접지 않고 바닥을 덮는 배치를 찾습니다. 덮을 수 없으면 'EI SAA'를 출력합니다.
문제
마티는 방의 천장을 칠하려고 한다. 페인트 방울이 바닥에 튀지 않도록 바닥을 덮어야 하는데, 이를 위해 판지 두 장이 있다. 하지만 판지는 나중에도 필요하므로 자르거나 접으면 안 된다. 판지 한 장으로 바닥 전체를 덮을 수 있다면 나머지 판지는 쓰지 않는다.
방과 판지는 모두 직사각형이다. 방의 크기는 cm이고, 첫 번째 판지의 크기는 cm, 두 번째 판지의 크기는 cm이다.
두 판지로 바닥 전체를 한 번에 덮을 수 있는지 확인하라. 판지는 회전해도 되고 서로 일부가 겹쳐도 된다. 다만 판지가 방의 가장자리 밖으로 나가면 안 된다. 덮는 것이 가능하면 XY 좌표계에서 판지의 위치를 구하라. 이때 방의 대각선 꼭짓점은 과 이다. 가능한 배치가 여럿이면 그중 하나를 출력한다.
입력
첫 줄에 방의 크기 와 가 공백으로 구분된 정수로 주어진다 (). 둘째 줄에는 첫 번째 판지의 크기 과 이, 셋째 줄에는 두 번째 판지의 크기 와 가 같은 형식으로 주어진다 ().
출력
바닥을 덮을 수 없으면 한 줄에 'EI SAA'를 출력한다.
두 판지를 사용하면 각 줄에 네 정수를 출력한다. 첫 줄에는 첫 번째 판지의 왼쪽 아래 꼭짓점 좌표 , 과 오른쪽 위 꼭짓점 좌표 , 를 쓴다. 둘째 줄에는 두 번째 판지의 꼭짓점 좌표 , , , 를 쓴다.
첫 번째 판지만 사용하면 첫 줄에 그 꼭짓점 좌표를 쓰고 둘째 줄에 'Z'를 쓴다. 두 번째 판지만 사용하면 첫 줄에 'Z'를 쓰고 둘째 줄에 두 번째 판지의 꼭짓점 좌표를 쓴다.