IOI 1995 day1 1- 직사각형 싸기(Packing Rectangles) > 문제은행 : 정보올림피아드&알고리즘




2599 : 직사각형 싸기(Packing Rectangles)

제한시간
1000 ms   
메모리제한
0 MB   
해결횟수
6 회   
시도횟수
21 회   

문제

직사각형 네 개가 있다. 

이것들을 서로 겹치지 않게 적당히 배치한 뒤 네 개를 모두 포함하는 직사각형으로 둘러쌌을 때, 

이 직사각형이 가질 수 있는 최소 넓이를 구하는 프로그램을 작성하라.

네 직사각형과 이를 둘러싸는 직사각형은 변이 서로 나란히 있어야 한다.

 

  

 

위 그림은 네 직사각형을 싸는 여섯 가지 방법을 나타내고 있다. 이 방법은 최소한의 기본적인 방법이다. 

이들을 회전시키거나 상하 좌우를 바꾸면 다른 방법이 만들어진다.

넓이를 최소로 하면서 네 직사각형을 싸는 직사각형은 여러 개가 있을 수 있다. 

답안 프로그램은 이 방법을 모두 계산하여 출력해야 한다.


입력형식

입력은 네 줄에, 각 직사각형의 가로, 세로의 변 길이 a, b(1≤a,b≤50)가 입력된다.


출력형식

출력의 첫 줄에 둘러쌀 수 있는 최소의 넓이, 다음 줄부터 쌀 수 있는 직사각형의 가로, 세로 길이를 가로 길이를 기준으로 정렬하여 출력한다. (가로 ≤ 세로)


입력 예

1 2
2 3
3 4
4 5

출력 예

40
4 10
5 8


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP