QUADAREA - Maximal Quadrilateral Area

You are trying to build a house, but unfortunately you currently have only four available walls with side lengths a, b, c, and d. You want your house to be as big as possible, so you would like to know the largest possible area of any quadrilateral you can construct with these four side lengths.

Input

The first line contains the integer T (1 ≤ T ≤ 2,000), the number of tests. Each test contains a single line with four real numbers: a, b, c, and d (0 < a, b, c, d < 1,000). Note that it will always be possible to form a valid quadrilateral with these lengths; that is, the sum of any three side lengths will be strictly larger than the other one.

Output

For each test case, print a single line containing the largest possible area. Your output will be accepted if it is within 0.01 of the official answer.

Example

Input:
2
1 2 1 2
0.5 0.5 0.5 0.5

Output:
2.00
0.25

For the first test case, it is optimal to construct a rectangle, and for the second, a square is optimal.


Added by:Neal Wu
Date:2008-05-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO

hide comments
2015-07-04 08:56:56
no logic at alll.....just a formula........not interesting
2015-06-08 08:42:41 Ankush
Brahmagupta \m/
2015-04-27 11:14:00 gohanssj9
Exactly Abhishek...Thanks to Brahmagupta...but the problem doesnt mention if its cyclic or not...that is a confusion
2015-04-05 23:20:49 Jerry Goyal
how to know whether it's a cyclic quad.?
2015-04-04 21:05:22 Abhishek Kainth
Thanks to Brahmagupta!! :D
2014-05-17 07:21:11 pvkcse
just a four lines of code in python and AC at first attempt...!!!
2014-03-13 13:47:19 RAJAT SINGH
got AC in first attempt easiest problem in spoj .....if you know some math
2014-02-17 15:42:31 ppppppp
use double dont use float in c,c++
2014-01-21 19:25:28 Aragon!!!
just a formula.. :) ...
2014-01-17 18:46:38 Praveen
My 25th problem on SPOJ...:)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.