시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB177675.000%

문제

In your greenhouse you have a number of plants which you need to water.

Each of the plants takes up an area which is a circle. No two of the plants overlap or touch each other.

You are going to buy two sprinklers. Each of the sprinklers will spray everything within a circle of radius R with water.

One of the sprinklers will run in the morning, and one will run at night. For you to be satisfied that a plant will get enough water, either the whole area of the plant must be watered in the morning, or the the whole area of the plant must be watered at night. So each of the circles representing a plant must be completely in one or both of the two circles representing the area the sprinklers can water. 

Given the location and radius of each of the plants, find the minimum radius R so that it is possible to place the two sprinklers to water all the plants. The sprinklers will be installed on the ceiling, so a sprinkler's position can be inside the area of a plant.

입력

  • One line containing an integer C, the number of test cases in the input file.

For each test case, there will be:

  • One line containing N, where N is the number of plants you have.
  • N lines, one for each plant, containing three integers "X Y R", where (XY) are the coordinates of the center of the plant, and R is the radius of the plant.

Limits

  • All numbers in the input file are integers.
  • 1 ≤ X ≤ 1000
  • 1 ≤ Y ≤ 1000
  • 1 ≤ R ≤ 100
  • 1 ≤ C ≤ 10
  • 1 ≤ N ≤ 3

출력

For each test case:

  • One line containing the string "Case #x: R" where x is the number of the test case, starting from 1, and R is the minimum radius of the sprinklers.

Any answer with absolute or relative error of at most 10-5 will be accepted.

예제 입력 1

5
3
20 10 2
20 20 2
40 10 3
3
20 10 3
30 10 3
40 10 3
5
100 100 1
140 100 1
100 130 1
100 500 1
150 500 1
8
100 100 1
110 100 1
100 110 1
110 110 1
200 200 1
210 200 1
200 210 1
210 210 1
4
100 100 1
200 100 1
200 103 1
300 103 1

예제 출력 1

Case #1: 7.000000
Case #2: 8.000000
Case #3: 26.000000
Case #4: 8.071067
Case #5: 51

힌트

In the first case, a sprinkler of radius at least 7 centered at (20,15) will water the first two plants. A sprinkler of radius at least 3 will water the plant at (40,10).

In the second case, one of the two sprinklers will need a radius of at least 8. Note that the plant at (30,10) must be covered entirely by one of the two sprinklers.

출처

Contest > Google > Code Jam > Google Code Jam 2009 > Round 2 D1번

채점 및 기타 정보

  • 예제는 채점하지 않는다.