중심
메모리 제한1024 MB
평면 위 N개 점에 대해 체비쇼프 거리에 가중치를 곱한 합을 최소로 하는 중심을 찾아 그 최솟값을 구한다.
문제
평면 위에 N개의 가중치가 있는 점이 있다. 점 i는 (Xi, Yi)에 있고 가중치는 Wi이다.
이 문제에서는 이 점들의 특별한 중심을 찾아야 한다. 중심은 max(|X-Xi|, |Y-Yi|)*Wi의 합을 최소로 만드는 점 (X, Y)이다.
입력
입력은 정확히 하나의 정수 T를 포함하는 한 줄로 시작한다. T는 테스트 케이스의 수이다. 이어서 T개의 테스트 케이스가 주어진다.
각 테스트 케이스는 정수 N을 포함하는 한 줄로 시작한다. 이어서 N개의 줄이 주어진다. 각 줄은 공백으로 구분된 세 개의 실수 Xi, Yi, Wi를 포함한다. Xi, Yi, Wi는 소수점 아래 정확히 2자리이다.
출력
각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 중심 (X, Y)에 대한 max(|X-Xi|, |Y-Yi|)*Wi의 합이다.
y는 정답과의 절대 또는 상대 오차가 10-6 이내이면 정답으로 인정된다.
제한
- 1 ≤ T ≤ 10.
- -1000.00 ≤ Xi ≤ 1000.00.
- -1000.00 ≤ Yi ≤ 1000.00.