SQDIFF - Area Difference

A gardener bought two sprinklers for his new garden. Each sprinkler moistens the soil around a circle with known radius. One will be working in the morning and the other in the evening. To plan how many plants of different species is better to plant, the gardener wants to know what area of the garden will be watered only in the morning, only in the evening or both in the morning and in the evening. After some searching on the Internet, he found a formula for calculating the area of intersection of circles, but for some reason the formula that would help to calculate the remaining two areas was not found.

Input

The first line contains T (1 <= T <= 1000) - the number of tests. The next T lines contain six integers x1, y1, r1, x2, y2 and r2 (0 <= xi, yi, ri <= 10000) - coordinates and radii of the first and second sprinkler, respectively.

Output

For each test case print the absolute value of the difference between the the area that is going to be watered only in the moring and the area that is going to be watered only in the evening rounded to two decimals after the point. Your score is the source length.

Example

Input:
1
2 2 4 5 2 3

Output:
21.99


Added by:Spooky
Date:2010-03-09
Time limit:3s
Source limit:2000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: SCM qobi
Resource:Advancement Spring 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin

hide comments
2012-08-12 17:59:32 Hallvard Norheim Bø
My java solution gives TLE now, that is strange. 1000 testcases run in 0.23 seconds on ideone.com, and here the time limit is 1 second.

edit: after time limit increase from 1 to 3 sec it passed, with time used reported to be 0.99 sec :)


Last edit: 2012-08-21 17:09:40
2011-07-14 17:36:33 Piotr KÄ…kol
You would have to ask Spooky.
The best way to do it is imo to submit the program on main SPOJ and then ask in comments as here.
2011-07-14 10:37:28 Hallvard Norheim Bø
Why did #5378117 fail? The code runs just fine on ideone.com. Is it due to slightly different versions of Bash (4.0.35 vs 4.0.37)?
2010-10-24 21:44:18 Piotr KÄ…kol
@XeRon!X - Done. Thank You for Your honesty. :-)

Last edit: 2010-10-24 21:44:39
2010-10-24 21:06:55 XeRoN!X
Kindly rejudge my 61byte solution also. I think it will also not work with perl 5.12.
2010-09-15 19:58:48 Piotr KÄ…kol
I don't know why I could now and coundn't in the past but these two submissions with score 59 were rejudged (and got WA).
Sorry, Piotr and Christian (as Zoltan said it's because Perl 5.10 was changed to 5.12).

Last edit: 2010-09-15 19:59:04
2010-09-02 14:59:57 Zoltán Zámbori
It is a site level problem, not a task level. A language version change (in this case Perl 5.10 to 5.12) may introduce inequality between past and future submitters.

SQDIFF is just an example: in the past "implicit split()" was available (minus 3 strokes), but today nobody can post such a solution (WA).
2010-09-02 13:11:44 Piotr KÄ…kol
I can't. I can only do such things with my tasks. You have to ask Spooky (author of this task). Sorry.

Last edit: 2010-09-02 13:45:44
2010-09-01 19:34:44 Zoltán Zámbori
Piotr, please rejudge the top two (perl 59byte) code.
2010-08-12 09:27:30 Piotr KÄ…kol
1.01 (that's for further users because I see that You have already reached shortest code :-) congratulations! :-) ).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.