[2018 SCPC 본선]

터렛

터렛 혹은 미사일 터렛은 스타크래프트의 테란 종족의 대공 방어용 건물 종류이다.

터렛을 설치하면 설치된 지점에서 지정된 거리(탐지 거리라고 하자) 내에 들어오는 적을 탐지하여 미사일을 발사한다.

새로 발매된다는 루머가 있는 스타크래프트 3에서는 터렛의 탐지 거리를 사용자가 임의로 지정하여 각 터렛이 모두 다른 탐지 거리를 가지게 할 수 있다고 한다.

각 터렛의 탐지 영역은 원형이며 사용자는 이 탐지 영역의 반지름을 0 이상의 임의의 실수로 정할 수 있다. 

단, 여러 개의 터렛을 설치할 경우 다음과 같은 상황이 되면 터렛이 오작동하여 사용할 수 없게 된다.



1.    두 터렛의 탐지 영역이 서로 겹치는 경우, 두 터렛 모두 오작동하여 사용할 수 없게 된다. (단, 탐지 영역의 경계만 닿는 경우는 상관없다.)

2.    한 터렛의 탐지 영역 내에 다른 터렛이 들어가는 경우, 두 터렛 모두 오작동하여 사용할 수 없게 된다. (단, 탐지 영역의 경계에 다른 터렛이 위치한 경우는 상관없다.)



\(N\) 개의 터렛이 이미 설치되어 있을 때, 위와 같은 오작동 상황이 벌어지지 않는 한에서 가능한 탐지 영역의 면적의 최대치를 계산하는 프로그램을 작성하시오.

터렛은 모두 수평한 동일 직선 위에 위치한다고 가정하며, 따라서 이들의 위치는 \(x\)-좌표 하나로만 주어진다.

또한 원의 면적은 반지름의 제곱에 원주율을 곱한 값이므로 이 문제에서는 각 터렛의 탐지 거리의 제곱 값의 총합(원주율을 곱하지 않고)의 최댓값을 출력하도록 한다.

• 제한시간: 전체 테스트 케이스는 100개 이하이며, 전체 수행 시간은 2초 이내. (Java 4초 이내) 
  
  
  
    제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
  
    그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
  
    그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
  
    이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
  
    C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
  
    제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.
  
     ※ 언어별 기본 제공 소스코드 내용 참고
  
    만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
  
  
  
  - 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB

입력

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

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

이후 차례로  \(T\) 개의 테스트 케이스가 주어진다. \((1 ≤ T ≤ 100)\)

각 테스트 케이스는 첫 줄에 정수 \(N (2≤N≤200,000)\) 하나가 주어지며, 이는 입력으로 주어질 터렛의 개수를 의미한다.

두번째 줄에는 \(0\) 이상 \(10^9\) 이하의 정수 N개가 오름차순으로 정렬되어 주어지며, 두 정수 사이는 공백문자로 구분한다.

이 값들은 \(N\)개의 터렛의 위치의 \(x\)-좌표를 의미한다.

• 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 495점)
  
  
  
    주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
  
    각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
  
     ㆍ 그룹 1 (49 점) : 이 그룹의 테스트 케이스에서는 \(N≤500\)이고 터렛의 좌표 범위는 \(0\) 이상 \(10,000\)이하이다.
  
     ㆍ 그룹 2 (136 점) : 이 그룹의 테스트 케이스에서는  \(N≤2,000\) 이다.
  
     ㆍ 그룹 3 (81 점) : 이 그룹의 테스트 케이스에서는 터렛의 위치의 \(x\)-좌표를 순서대로 \(x_1,x_2,…,x_N\) 라 할 때, \(x_2-x_1≤x_3-x_2≤⋯≤x_N-x_{(N-1)}\)의 관계식을 만족한다.
  
     ㆍ 그룹 4 (229 점) : 이 그룹의 테스트 케이스에서는 별도의 제한이 없다.

출력

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

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

이때 \(C\)는 테스트 케이스의 번호이다.



그 다음 줄에 입력으로 주어진 터렛의 위치에 대해 단 하나의 터렛도 오작동하는 상황이 생기지 않도록 할 때, 가능한 탐지 거리의 제곱값의 총합의 최댓값을 실수 형태로 출력한다.

단, 정확한 값으로부터 \(10^{-9}\) 만큼의 절대오차 혹은 상대오차를 허용하여 정답으로 처리한다.

입출력예

입력
2 5 0 1 2 3 4 5 0 1 3 6 10

출력
Case #1 3.000000000 Case #2 21.000000000

돌아가기