Area of Circle Union X55040


Statement
 

pdf   zip

html

We want to calculate the area of the union of a set of circles. This is a problem that has some non-trivial algorithm for the exact computation. Instead, we would be satisfied by finding an approximation using a Montecarlo method. The ideas is as follows:

  • Calculate a bounding box around the circles.
  • Generate random points within the bounding box.
  • Count how many points are inside some circle.
[x=0.5mm,y=0.5mm] (15,15) circle[radius=15]; (30,30) circle[radius=25]; (35,12) circle[radius=12]; (50,30) circle[radius=15]; (70,10) circle[radius=7]; (80,15) circle[radius=10];
=⇒
[x=0.5mm,y=0.5mm] (15,15) circle[radius=15]; (30,30) circle[radius=25]; (35,12) circle[radius=12]; (50,30) circle[radius=15]; (70,10) circle[radius=7]; (80,15) circle[radius=10]; [dashed](0,0) rectangle ++(90,55);

Exam score: 2.5 Automatic part: 100%

Input

The input contains a set of cases. Each case specifies the number of circles, n≥ 0, and the number of random points generated for the Montecarlo approximation. After that, a list of n circles is specified, each one with the coordinates of the center, (x,y), and the radius. The coordinates and the radius are real numbers.

Output

For every case print the estimated area as a real number in free format.

Observation

There is no need to compute the exact area. The output will be considered correct if it is a good approximation of the area.

Public test cases

  • Input

    1 1000000
0 0 1

2 1000000
0 0 1
0 0 0.5

4 1000000
0 0 2
1 1 3
-1 1 4
0 -1.5 2.5

    Output

    3.14287
3.14187
59.4536
    • Information
    Author
    Professors de Info-FME
    Language
    English
    Official solutions
    C++
    User solutions