[2019 SCPC 1차 예선]

파이프

원형의 파이프 개가 있다.

각 파이프의 반지름을 안다고 하자. 파이프를 모두 같은 방향으로 놓으려고 한다.

즉, 파이프는 원으로 생각할 수 있다. 또, 모든 파이프는 바닥에 닿아 있어야 한다.

즉, 어떤 파이프든지 다른 파이프 위에 있어서 바닥과 떨어져 있으면 안된다.

파이프가 원으로 보이는 방향에서 보았을 때 놓았을 때 왼쪽 끝부터 오른쪽 끝까지의 거리를 가능한 최소화하라.



아래 그림은 5개의 파이프를 배치한 두가지 방법을 보여준다.

왼쪽 방법보다 오른쪽 방법의 왼쪽 끝에서 오른쪽 끝까지의 거리가 더 작음을 알 수 있다.








이 문제는 주최측이 계산한 답에 대한 비례로 점수가 주어진다. 아래 채점 방식을 확인하라.


입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 가 주어지고,

이후 차례로   개의 테스트 케이스가 주어진다. ( )

각 테스트 케이스의 첫 줄에는 파이프의 개수 이 주어진다. ( )

다음 줄에 각 파이프의 반지름이 개의 정수로 주어진다.

반지름은 1 이상 1,000,000 이하이다.

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.

다음 개의 줄에, 입력에 주어진 순서대로의 각 파이프 중심의 좌표를 출력한다. 파이프들의 위치는 어디이든 상관없으나 모든 좌표 값의 절대값이 이하라야 한다.

좌표 값은 실수로 적어도 소수점 이하 10자리까지 출력해야 정확한 채점을 보장할 수 있다. 

출력한 원들의 위치에 대해, 임의의 두 원을 잡았을 때 을 만족해야 점수가 주어진다.

입출력예

입력
2
5
290328 356166 438877 410830 219438
7
405391 510242 439253 547312 465626 534027 608087
출력
Case #1
1334579.04753950797021389008
2790350.17604429880157113075
620665.09850643284153193235
2025304.61457753228023648262
0.00000000000000000000
Case #2
0.00000000000000000000
6058220.07462551258504390717
2026643.68445300729945302010
3007272.94760193023830652237
4016911.88764336891472339630
5014221.98165024258196353912
993001.50456482195295393467

돌아가기