Back to Category
d012: [08.12] A - Red Areas
Keyword: Others, 陳伶志, PTC 2008

Difficulity: 1 | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 128 Times | Submit :638 Times | Clicks : 2652
Accepted : 38 Users | Submit : 44 Users | Accepted rate : 86%
Time Limit :5000 ms | Memory Limit : 64000 KBytes
Update : 2010-07-20 21:02

Content: English | Chinese(TW)

According to the reliable source, the terrorists have installed a number of bombs in the urban area of the Taike city, and they plan to detonate the bombs in the New Year’s Eve. It is believed that the bombs will create severe damages to the city, and it is very important for the government to take every possible action ASAP in order to minimize the potential damages.

Fortunately, after detailed investigation by the Army Special Forces, we have identified the location and the potential damage area (i.e., the Red Area) of each bomb. The Red Area of each bomb is a circle area centered at the bomb. We suppose there are N bombs. The i-th bomb is located at the coordinate (xi, yi), and the radius of the i-th bomb’s Red Area is ri.

The Taike city has decided to set up restriction lines to indicate all Red Areas, and now it is your task to figure out the length of the cords required to surround all Red Areas. Note that the Red Areas may be overlapped, thereby resulting a non-circle shape. Moreover, it is possible to have multiple isolated safe areas, which are not threatened by any of the bombs (i.e., not belong to any Red Areas), but surrounded by the Red Areas.

For instance, in Figure 1, there are two bombs in the city (located at (0, 0) and (2, 0)), and the Red Area of the two bombs are equal-sized with the radius equal to 2. The overall Red Area in this example can be surrounded by one cord with the length about equal to 16.76. Meanwhile, in Figure 2, there are eight bombs (located at (1, 1), (1, 3), (1, 5), (3, 1), (3, 5), (5, 1), (5, 3), and (5, 5) respectively), and the Red Area of each bomb has the same radius (equal to 1). The Red Areas result in an isolated safe area (i.e., the shaped area in Figure 2), in addition to the outer safe area. Therefore, the overall Red Area in this example can be surrounded by two cords (i.e., one for the isolated area, and the other one for the outer area) with the length about equal to 50.27 in total.

 Hint: The circumference of a circle can be obtained using the equation: L = 2πr, where π = 3.14159265 and r is the radius the of circle.

Technical Specification

1. N is an integer, and 1 ≤ N ≤ 100.
2. For the i-th bomb, it’s coordinates and radius are all integers. Moreover, −900 ≤ xi ≤ 900, −900 ≤ yi ≤ 900, and 0 < ri ≤ 20.
3. The location of each bomb must be distinct (i.e., they will not have the same coordinate values).

Input:

The first line of the input file contains an integer indicating the number of test cases to follow. For each test case, the first line contains one positive integer N representing the number of bombs in the city. In the following N lines, each line contains three integers: xi , yi , and ri , representing the coordinates and radius of the Red Area of the i-th bomb respectively.

Output:

Please output two numbers, with exactly one space between them, in one line for each test case. The first number a is a real number, and 0 < a < 10. The second number b is a non-negative integer, and a×10b represents the scientific notation of the length of the cords required to surround all Red Areas. Note that, the value of a should be round off to two digits after decimal.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
2 
0 0 2 
2 0 2 
8 
1 1 1 
1 3 1 
1 5 1 
3 1 1 
5 1 1 
5 3 1 
3 5 1 
5 5 1 

Sample Output :

1.68 1
5.03 1 

Hint :

click here to download the problem solving hint

Author :

陳伶志, PTC 2008

  Solve it!   Status Forum

C
C++
JAVA
PASCAL
5600. admin
(652ms, 340KB, 1309B)
49760. toi_201315
(2ms, 924KB, 2770B)
49745. toi_201322
(300ms, 8724KB, 1876B)

Program running time may be affected by various factors. Check server system environment information here