E - Everybody may get lost in space

08.01.2010
TrudnośćTrudnośćTrudnośćTrudność

Time limit: 16 s
Memory limit: 32 MB

As we all know, all essential systems of a space shuttle are ``redundantly replicated'' just in case. In the cold and empty space, the key question to a successful navigation is the centuries-old ``weremay?'' Luckily, in accordance to aforementioned rule, the shuttle's coordinates can be obtained from three independent sources. These systems provide not only $ x $, $ y $ and $ z $ coordinates, but also the bound $ b $ on observational error. The error applies to the distance from point $ (x,y,z) $, meaning that whenever a system reports $ (x,y,z) $, the correct shuttle's coordinates might be any $ (x',y',z') $ with $ \sqrt{(x-x')^2+(y-y')^2+(z-z')^2} \leq b $. Truth be told, it's not easy to determine the shuttle's position given as many as its three measures. Your task is to determine the volume of the (sub-)space in which the shuttle is possibly contained. At least one of the three systems is intact, but it might be the case that the others are broken.

Multiple Test Cases

The input contains several test cases. The first line of the input contains a positive integer $ Z \leq 10000 $, denoting the number of test cases. Then $ Z $ test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.

Single Instance Input

The input instance consists of three lines, each containing a single independent measure. Each measure consists of coordinates $ x,y,z \in [-10^9,10^9] $ and the observational error $ b \in [1,10^9] $ separated by single spaces.

Single Instance Output

Your program is to print out the volume of the (sub-)space in which the shuttle is possibly contained. Your result is going to be accepted if and only if it is accurate to within a relative or absolute value of at most $ 10^{-6} $.

Example

Input

2
0 0 0 10
19 0 0 10
23 0 0 10
0 0 0 10
12 0 0 10
18 0 0 10

Output

9602.0161463094
9334.7189713665
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com