TopCoder problem "Meteorites" used in SRM 346 (Division I Level Three)

Problem Statement


A terrible meteorite storm has crashed into a large part of your city. As a chief police officer, you are in charge of closing down the perimeter of the damaged area to prevent citizens from falling into a crater. Each meteorite left a crater in the form of a circle. Several craters can touch each other, intersect, or be inside one another. You need to calculate the length of danger tape needed to cover the perimeter of the union of all craters.

You will be given three int[]s, x, y and r where the ith element of each contains the x and y coordinates of the center and the length of the radius of each crater. Return the length of the perimeter of the union of all those circles. Note that even if an area is completely surrounded by craters, its perimeter must be taken into account. See example 2 for further clarification.



Parameters:int[], int[], int[]
Method signature:double perimeter(int[] x, int[] y, int[] r)
(be sure your method is public)


-The returned value must be accurate to within a relative or absolute value of 1e-9.


-x will contain between 1 and 50 elements, inclusive.
-x, y and r will all contain the same number of elements.
-Each element of x and y will be between -1000000 (-106) and 1000000 (106), inclusive.
-Each element of r will be between 1 and 1000000 (106), inclusive.
-No two craters will be equal (i.e., any two craters will have different location and/or different size).


Returns: 63.72326520248748
Returns: 135.3757009200326
Returns: 2008.3301227325105
Even when the middle area is inaccesible from the outside because it is surrounded by craters, its perimeter must be included in the final result.
Returns: 628318.5307179586
Every crater is inside the big one.

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories: