HowBigIsIt? ¶
이안이 캘리포니아로 이사를 가기 위해 짐을 싸고 있는데, 지금까지 모은 원도 포장해야 한다. 일련의 원이 주어졌을 때 그 원들을 모두 집어넣을 수 있는 가장 작은 직사각형 상자의 크기를 구하는 프로그램을 만들어야 한다.
모든 원은 상자 바닥에 닿아야 한다. 아래에 원을 직사각형 상자에 집어넣는 방법이 나와있는데, 이 그림에 나온 배치법은 최적의 방법이 아닐 수도 있다. 조금만 생각해보면 알겠지만, 최적화된 방법이라면 모든 원들이 서로 맞닿아있어야만 한다.
http://online-judge.uva.es/p/v100/p10012.gif
http://online-judge.uva.es/p/v100/p10012.gif
Input ¶
첫째 줄에는 테스트 케이스의 개수를 나타내는 양의 십진수 n(n≤50)이 입력된다. 그 밑으로 n줄에 걸쳐서 일련의 수들이 입력되는데, 각 수는 스페이스로 구분된다. 각 줄의 첫째 줄은 8 이하의 양의 정수 m이며, 그 줄에 몇 개의 수가 더 들어있는지를 나타낸다. 그 뒤로 m 개의 수가 입력되는데, 각각 상자에 집어넣어야 할 원의 반지름을 의미한다. 이 수들은 꼭 정수가 아니어도 된다.
output ¶
각 테스트 케이스에 대해 원들을 모두 포장할 수 있는 가장 작은 직사각형 상자의 크기를 출력한다. 각 케이스에 대한 결과가 서로 다른 줄에 출력되어야 하며, 소수점 아래로 셋째 자리까지 출력한다. 숫자가 1보다 작지 않은 경우에는 앞에 불필요한 0을 덧붙이지 않는다(1 미만인 경우에는 0.543 같은 식으로 앞에 0을 하나 붙여준다).
