Hide

Problem G
The Worm in the Apple

Willy the Worm was living happily in an apple – until some vile human picked the apple, and started to eat it! Now, Willy must escape!

Given a description of the apple (defined as a convex shape in 3D space), and a list of possible positions in the apple for Willy (defined as 3D points), determine the minimum distance Willy must travel to get to the surface of the apple from each point.

Input

There will be a single test case in the input. This test case will begin with a line with a single integer $n$ ($4 \le n \le 1\, 000$), which tells the number of points describing the apple.

On the next $n$ lines will be three integers $x$, $y$ and $z$ ($-10\, 000 \le x,y,z \le 10\, 000$), where each point $(x,y,z)$ is either on the surface of, or within, the apple. The apple is the convex hull of these points. No four points will be coplanar.

Following the description of the apple, there will be a line with a single integer $q$ ($1 \le q \le 100\, 000$), which is the number of queries – that is, the number of points where Willy might be inside the apple. Each of the following $q$ lines will contain three integers $x$, $y$ and $z$ ($-10\, 000 \le x,y,z \le 10\, 000$), representing a point $(x,y,z)$ where Willy might be. All of Willy’s points are guaranteed to be inside the apple.

Output

For each query, output a single floating point number, indicating the minimum distance Willy must travel to exit the apple. The absolute error of your answer should be less than $10^{-4}$.

Sample Input 1 Sample Output 1
6
0 0 0
100 0 0
0 100 0
0 0 100
20 20 20
30 20 10
4
1 1 1
30 30 35
7 8 9
90 2 2
1.0
2.88675134594812
7.0
2.0

Please log in to submit a solution to this problem

Log in