Spherical Shield Hole Optimization

The isolation shield is a vital component used to protect the scanner (and not the tractor!) from damage by stray cosmic rays originating from other universes. For simplicity, the shield before cutting can be regarded as a unit sphere as shown in the figure.

We plan to carry out \( N \ (1\le N \le 10^6) \) observation tasks. For the \( i\)-th observation, we depart from the origin and scan a meteorite that is modeled as a sphere. Its center is at \( (x_i,y_i,z_i) \) and it has radius \( r_i \) (with \( -10^6 < x_i,y_i < 10^6 \) and \( 0<r_i<z_i<10^6 \)).

Each observation requires that the entire meteorite be visible through a circular hole opened on the shield. In our model the meteorite (i.e. its projection onto the upper hemisphere of the unit sphere) is a spherical cap. More precisely, from the origin the meteorite centered at \( (x_i,y_i,z_i) \) with radius \( r_i \) appears as a spherical disk (or cap) on the unit sphere with center \( \mathbf{v}_i=\frac{(x_i,y_i,z_i)}{d_i} \) (where \( d_i=\sqrt{x_i^2+y_i^2+z_i^2} \)) and angular radius \( \alpha_i=\arcsin\frac{r_i}{d_i} \) (in radians).

Your task is to open a circular hole on the shield (i.e. on the spherical surface) with the smallest possible radius (measured as the great‐arc length). This hole must cover the union of all the meteorite projections on the upper hemisphere. Equivalently, if the chosen covering circle has a half–angle (measured at the sphere’s center) of \( \omega \) (with \( 0< \omega <\frac{\pi}{2} \)), then for every meteorite \( i \) the condition

[ \mathrm{dist}(\mathbf{c},\mathbf{v}_i)+\alpha_i \le \omega ]

must hold, where \( \mathrm{dist}(\mathbf{c}, \mathbf{v}_i) \) is the spherical (great–arc) distance between the center \( \mathbf{c} \) of the hole and the meteorite’s projected center \( \mathbf{v}_i \). Finally, you are to output

[ \left\lfloor \frac{\omega}{\pi/2}\times 10^5 \right\rfloor ]

where \( \lfloor \cdot \rfloor \) denotes the floor function.

inputFormat

The first line contains an integer \( N \), the number of observation tasks. Each of the following \( N \) lines contains four space-separated numbers: \( x_i\ y_i\ z_i\ r_i \), representing the coordinates of the meteorite’s center and its radius.

outputFormat

Output a single integer: the value \( \left\lfloor\frac{\omega}{\pi/2}\times10^5\right\rfloor \) where \( \omega \) is the minimum half–angle (in radians) of the covering spherical cap.

sample

1
0 0 10 1

6378