Circles
시간 제한8초메모리 제한1024 MB
반지름 0에서 같은 속도로 자라는 원들이 다른 원과 닿으면 멈출 때, 최종적으로 모든 원이 차지하는 넓이의 합을 구한다.
문제
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.