Grid ---- A `grid' (in the sense described here) is a geometric data base that stores a set of `points' in a fashion that makes it easy to look up which points are near a query point. It is possible to represent geometric objects as points and use a grid to look up which objects are near a query point. The grids we are concerned with are binary trees in which each node is associated with a rectilinear region in (cx, cy, cz, r) 4-dimensional space. Here (cx, cy, cz) is the center of a 3-dimensional sphere of radius r, so the 4-dimensional point represents a 3-sphere. Each child is associated with a subregion of its par- ent's region, so that the regions of the two children of a node are disjoint and their union is the parent region. The child regions are made by intersecting the parent region with the halfspaces d <= v and d > v, for some real number v and coordinate d. Here d may be cx, cy, cz, or r. Leaves of the grid contain sets of 4-dimensional points. In this problem we shall not be concerned with these sets. You are given a grid and a set of queries. Each query consists of a point p and a distance R, and the answer is the subtree of nodes whose regions contain a 4D point (cx,cy,cz,r) representing a sphere that is at most distance R from p, i.e., ||p-(cx,cy,cz)|| <= r+R. If you think about it you will find that the nodes of the desired subtree are those whose 4D regions intersect a 4D cone whose axis is parallel to the r-direction and whose r = C slice is a 3-sphere of radius R+C and center p. Input ----- For each of several test cases, a line containing just the test case name, followed a line containing cxmin cxmax cymin cymax czmin czmax rmin rmax followed by lines containing a representation of the grid, followed by one or more query lines, followed by a line containing just a `*'. The region of the grid root is cxmin < cx <= cxmax cymin < cy <= cymax czmin < cz <= czmax rmin < r <= rmax The grid representation has the syntax: ::= # | d/v(,) d ::= cx | cy | cz | r v ::= a real number Here represents a tree node, # represents a leaf, the first in d/v(,) represents the left child, and the second represents the right child. The left child region is made by intersecting the parent region with the halfspace d <= v, and the right child region is made by intersecting with d > v. Whitespace, including line feeds, is allowed only after `(' and `,'. A query is represented by a single line containing px py pz R where (px, py, pz) is the query point and R the query distance. No grid will have more than 127 nodes. There will be no more than 1000 queries among all the test cases taken together. For each test case and query: cxmin < cxmax cymin < cymax czmin < czmax 0 <= rmin < rmax 0 <= R All input numbers are in the range [-1000, +1000] and have at most 3 decimal places. Input ends with an end of file. Output ------ For each test case, first a line containing an exact copy of the test case name line, and then for each query p, R, exactly one line (possibly very long) containing a representation of the subtree of grid nodes whose regions contain points that represent spheres within distance R of point p. This subtree is represented by the syntax: ::= # | * | (,) and is a pruned version of the grid made by omitting the `d/v's and representing omitted children by `*'. Also there may not be ANY whitespace within the query output line. The input will be such that the output is unambiguous. Sample Input ------ ----- -- SAMPLE 1 -- -10 10 -10 10 -10 10 0 2 cx/0(cx/-5(#,#),cx/5(#,#)) -10 0 0 0 -5 0 0 0 -2.5 0 0 0 -1 0 0 0 +1 0 0 0 +2.5 0 0 0 +5 0 0 0 +10 0 0 0 * -- SAMPLE 2 -- -10 10 -10 10 -10 10 0 2 cx/5(cy/5(cz/5(r/1(#,#), r/1(#,#)), cz/5(r/1(#,#), r/1(#,#))), cy/5(cz/5(r/1(#,#), r/1(#,#)), cz/5(r/1(#,#), r/1(#,#)))) -13 -5 5 0.1 -12 -5 5 0.1 1 -5 5 0.1 1 -5 3 0.1 1 1 1 3.1 1 1 1 2.1 * Sample Output ------ ------ -- SAMPLE 1 -- ((#,*),*) ((#,#),*) ((*,#),*) ((*,#),(#,*)) ((*,#),(#,*)) (*,(#,*)) (*,(#,#)) (*,(*,#)) -- SAMPLE 2 -- * ((((*,#),(*,#)),*),*) ((((#,#),(#,#)),*),*) ((((#,#),(*,#)),*),*) ((((#,#),(#,#)),((#,#),*)),(((#,#),*),*)) ((((#,#),(*,#)),((*,#),*)),(((*,#),*),*)) Remarks ------- In real applications, the spheres bound more complex objects which are inspected further once it is determin- ed that their bounding spheres are close enough to the observation point. Also, p and part of R may themselves represent a sphere bounding a complex object. Lastly, in a real application, the algorithm to select grid nodes in the subtree may be simplified to be faster at the cost of including some nodes that do not belong. But you must NOT simplify for this problem, which requires precise computation of intersections. Reference --------- Algorithms & Data Structures, with applications to graphics and geometry, Jurg Nievergelt and Klaus H. Hinrichs, 23.5. File: grid.txt Author: Bob Walton Date: Sun Oct 5 05:53:46 EDT 2014 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2014/10/05 09:56:22 $ $RCSfile: grid.txt,v $ $Revision: 1.9 $