SPOJ.com - Problem CIRCLE

CIRCLE_H - Three Circle Problem (HARD)

no tags

Given 3 distinct circles with positive integer radius R1, R2, and R3, and arranged like in the picture below:

Three Circle Problem

Now, your task is to compute radius of small circle that can be created like yellow circle in the picture above. All circles in the picture above tangent each other.

Input

The first line in the input data, there is an integer T(0 < T ≤ 10⁵) denoting number of test cases, than T lines follow.

For each lines, there are three integer R1, R2, and R3, (0 < {R1, R2, R3} < 10³⁰) denoting radius of each circle like in the picture above.

Output

For each test case, output radius of small circle that can be made, like in the picture above. Truncate the output to 50 digit after decimal point.

Example

Input:
3
1 1 1
10 10 10
23 46 69

Output:
0.15470053837925152901829756100391491129520350254025
1.54700538379251529018297561003914911295203502540253
6.00000000000000000000000000000000000000000000000000

You can see my submission history and time record for this problem: here

Submit solution!

hide comments

< Previous 1 2 Next >

	Francky: 2013-04-06 11:48:50 If you want to learn something new, I recommend Matters computational, and Modern Computer Arithmetic. These are my main sources. Please share other useful links if you know some. edit : "Warning: This problem maybe impossible for slow languages (e.g. java,python,pike).", or maybe easier ;-). Ans: thanks for your sources, I think it will be very useful and congratulations, your code is insane ;-) superfast... Seems that I fail to set a problem that 'need big integer operation' and 'only feasible with fast language' :-( now I think there's no difference between this and medium version. Should I remove one of that problem? Oh, I forgot, You can do that if you want :-) --ans(francky)-->I thought about that too, but I don't have a final answer. I let you choose on that point, no problem for me, I don't seek for points. Ans(Tjandra): If you have final answer, and the answer is one of MEDIUM or HARD version should be hidden, I choose MEDIUM version that should be hidden and keep the HARD version (but I let you to do that, also I want to know what happen if one of my problem hidden by EB member).. Btw I see your code is not optimal there still some room for optimization: here the 2.16s py3 and 2.65s py2 is the result of your insane code + my small optimization.. ;-) --ans(francky)--> Done in under 2s, this part was not fully optimized, it's true. I still know some other little tricks... The medium edition should rather go to tutorial, not hidden. Done. Last edit: 2013-04-06 21:26:29
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-04-06 00:04:04 ~~Warning: This problem maybe impossible for slow languages (e.g. java,python,pike). But i still allow submission with all languages because maybe there are faster method to compute the answer.~~ (my convergence approximation formula is not the best).. Also my AC C code uses slow bignum/float operation, I'm weak to deal with big number. I hope I can learn something new :-) Last edit: 2013-04-06 18:11:03

Submit solution!

Added by:	Tjandra Satria Gunawan
Date:	2013-04-05
Time limit:	10s
Source limit:	10000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own Problem