There are many strange fountains in Love River, a famous site in Kaohsiung. These fountains are arranged in a line and the shape of these fountains are all circles. Note that they can intersect each other.
The government wants to know the total area covered by these fountains, so you were requested to calculate it. You're given only 5 hours only, however.
Whoops!! Time's ticking, better calculate it quick!
Assume the centers of all fountains are located on a line.
Given the position of the centers (as coordinates on the line) and the radius of each fountains, calculate the total area covered.
The first line has an integer T as the number of testcases.
Each testcase starts with an integer n, denoting the number of fountains in the river. Then n lines follow, where the i'th line contains two real numbers xi and ri separated by exact one space, denoting the i'th fountain's position and radius.(you can imagine all fountains are located in a one-dimensional coordinate system).
T<=50
n<=200000
0<=xi,ri<=1000 for all i
n<=1000 for for 80% of test cases
For each testcase, you have to print a real number as answer.
3 1 0 1 3 0 2 1 1 5 1 2 4 5 10 5
3.141593 15.707963 134.714872
Info: 本題輸出為浮點數，絕對或相對誤差 1e-6 以下視為正確
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|