Circles

There are n magical circles on a plane. They are centered at (x1, y1),(x2, y2), . . . ,(xn, yn), respectively. In the beginning, the radius of each circle is 0, and the radii of all magical circles will grow at the same rate. When a magical circle touches another, then it stops growing. Write a program to calculate the total area of all magical circles at the end of growing.

The first line contains an integer n to indicate the number of magical circles. The i-th of the following n lines contains two space-separated integers xi and yi indicating that the i-th magical circle is centered at (xi, yi).

A relative error of 10−6 is acceptable.

Output the total area of the circles.

• 2 ≤ n ≤ 2000
• xi, yi ∈ [−109, 109] for i ∈ {1, 2, . . . , n}.
• All (xi, yi)’s are disinct points.