중심

평면에 가중치가 있는 N개의 점이 있다. 점 i는 ($X_{i}$, $Y_{i}$)에 있으며 가중치 $W_{i}$를 가진다.

이 문제에서는 이 점들의 특별한 중심을 찾아야 한다. 중심은 max(|X-$X_{i}$|, |Y-$Y_{i}$|)*$W_{i}$의 합이 최소가 되는 점 (X, Y)이다.

제한

1 ≤ T ≤ 10. 메모리 제한: 1GB. -1000.00 ≤ $X_{i}$ ≤ 1000.00. -1000.00 ≤ $Y_{i}$ ≤ 1000.00.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 20초. 1 ≤ N ≤ 100; 모든 i에 대해 $W_{i}$ = 1.0이다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 40초. 1 ≤ N ≤ 10000; 모든 i에 대해 1.0 ≤ $W_{i}$ ≤ 1000.0이다.

입력은 테스트 케이스의 수인 정수 T를 정확히 하나 포함하는 한 줄로 시작한다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 N 하나를 포함하는 한 줄로 시작한다. 이어서 N개의 줄이 주어진다. 각 줄에는 공백으로 구분된 세 실수 $X_{i}$, $Y_{i}$, $W_{i}$가 주어진다. $X_{i}$, $Y_{i}$, $W_{i}$은 소수점 아래에 정확히 2개의 자릿수를 가진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 중심 (X, Y)에 대한 max(|X-$X_{i}$|, |Y-$Y_{i}$|)*$W_{i}$의 합이다.

y이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고한다.