407283: GYM102741 K Crafty Explosions

MC Matthew and Demolition Dan are playing their favorite Lego style adventure game! To spice up their vanilla crafting experience, they decided to add a mod enabling the creation of custom TNT. Matthew has placed $$$N$$$ pieces of modded TNT, which we will consider as singular points $$$(x_i, y_i, z_i)$$$, in his world. Each piece of TNT has a volatility constant of $$$v_i$$$ (not necessarily an integer), which is proportional to how powerful of a blast it can produce and how sensitive it is to disturbances in its surroundings (namely other TNT exploding). Demolition Dan has been challenged by MC Matthew to place a single piece of TNT to trigger all of the pre-placed TNT at the same time (this means that Dan cannot use chain reactions to trigger some subset of Matthew's TNT, which will then subsequently trigger the rest of the already placed TNT). Note that Dan does not necessarily need to choose a lattice point as his location for placement, and multiple pieces of TNT can be placed at the same coordinates.

If Dan places TNT at $$$(x, y, z)$$$, and one of Matthew's TNT pieces is at $$$(x_i, y_i, z_i)$$$, then the volatility of Dan's TNT must be at least

The higher the volatility constant of TNT, the more expensive it is to craft it. Can you help Dan find the position for his TNT that minimizes the volatility required, and output that volatility constant?

The first line of input will contain a single integer $$$N$$$ ($$$1 \leq N \leq 20000$$$), the number of pieces of TNT that MC Matthew has placed down. The next $$$N$$$ lines of input will contain four space separated integers $$$x_i$$$, $$$y_i$$$, $$$z_i$$$, and $$$v_i$$$ ($$$0 \leq x_i, y_i, z_i \leq 10^6$$$, $$$1 \leq v_i \leq 10^6$$$) representing the coordinates of a TNT piece and its volatility.

Output the minimum volatility constant necessary to complete the detonation. Answers with a relative or absolute error of at most $$$10^{−6}$$$ will be considered correct.

4
0 0 0 1
1 2 0 1
3 4 0 1
2 1 0 1

3.50000000

1
1 1 1 1

0.00000000

3
1 0 0 1
2 1 1 4
3 2 3 2

2.33333333