Connection Status:
Competition Arena > Meteorites

Meteorites

SRM 346 · 2007-04-24 · by soul-net

SRM 346 · 2007-04-24 · by soul-net · Geometry
Class Name: Meteorites
Return Type: double
Method Name: perimeter
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

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.

Notes

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

Constraints

  • 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).
Examples
0)
{0,10}
{0,0}
{6,7}
Returns: 63.72326520248748
1)
{-10,-10,-10,0,0,0,10,10,10}
{-10,0,10,-10,0,10,-10,0,10}
{7,7,7,7,7,7,7,7,7}
Returns: 135.3757009200326
2)
{-100,100,100,-100}
{-100,-100,100,100}
{110,110,110,110}
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.

3)
{0,0,0,0}
{0,0,0,0}
{1,2,3,100000}
Returns: 628318.5307179586

Every crater is inside the big one.

4)
{0,0,123,345,437,9,087,32,67,8,2514,376,1400}
{0,1,67543,86,2,56,1453,45,4356,4,634,24,1109}
{56,56,345,834,724,934,513,52,452,354,541,541,890}
Returns: 18640.610497639977

Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Meteorites with a public method double perimeter(vector<int> x, vector<int> y, vector<int> r) · 80 test cases · 2 s / 256 MB per case

Submitting as anonymous