eolymp
bolt
Try our new interface for solving problems
Məsələlər

The Worm in the Apple

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 \textbf{3D} space), and a list of possible positions in the apple for Willy (defined as \textbf{3D} points), determine the minimum distance Willy must travel to get to the surface of the apple from each point. \InputFile There will be several test cases in the input. Each test case will begin with a line with a single integer \textbf{n} (\textbf{4} ≤ \textbf{n} ≤\textbf{1000}), which tells the number of points describing the apple. On the next \textbf{n} lines will be three integers \textbf{x}, \textbf{y} and \textbf{z} (\textbf{-10000} ≤ \textbf{x}, \textbf{y}, \textbf{z} ≤ \textbf{10000}), where each point (\textbf{x}, \textbf{y}, \textbf{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 \textbf{q} (\textbf{1} ≤ \textbf{q} ≤ \textbf{100000}), which is the number of queries -- that is, the number of points where Willy might be inside the apple. Each of the following \textbf{q} lines will contain three integers \textbf{x}, \textbf{y} and \textbf{z} (\textbf{-10000} ≤ \textbf{x}, \textbf{y}, \textbf{z} ≤ \textbf{10000}), representing a point (\textbf{x}, \textbf{y}, \textbf{z}) where Willy might be. All of Willy’s points are guaranteed to be inside the apple. The input will end with a line with a single \textbf{0}. \OutputFile For each query, output a single floating point number, indicating the minimum distance Willy must travel to exit the apple. Output this number with exactly \textbf{4} decimal places of accuracy, using standard \textbf{5} up / \textbf{4} down rounding (e.g.\textbf{2.12344} rounds to \textbf{2.1234}, \textbf{2.12345} rounds to \textbf{2.1235}). Output each number on its own line, with no spaces, and do not print any blank lines between answers.
Zaman məhdudiyyəti 20 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #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
0
Çıxış verilənləri #1
1.0000
2.8868
7.0000
2.0000
Mənbə The University of Chicago Invitational Programming Contest 2012 15 April 2012