This page is still under construction.

Parts of this page are still being built. What you see may change.

Weird Flecks, But OK

Interview

Time limit3sMemory limit1024 MB

Summary
Given 3D points in a cube, find the smallest drill diameter so a bit entering perpendicular to a face removes all points, i.e. the smallest enclosing circle of the points projected onto each of the three coordinate planes.
Level

Medium5 of 10

Topics
Geometry, Binary search, Brute force, Implementation
Solved
No attempts yet

Problem

An artist who wanted to create an installation where his works appeared to be floating in midair has cast a large cube of clear acrylic to serve as a base. Unfortunately, during the casting, some small flecks of dirt got into the mix, and now appear as a cluster of pinpoint flaws in the otherwise clear cube.

He wants to drill out the portion of the cube containing the flaws so that he can plug the removed volume with new, clear acrylic. He would prefer to do this in one drilling step. For stability's sake, the drill must enter the cube perpendicular to one of its faces.

Given the (x,y,z)(x,y,z) positions of the flaws, and treating the size of the flaws as negligible, what is the smallest diameter drill bit that can be used to remove the flaws in one operation?

The drill may enter any one of the cube faces, but must be positioned orthogonally to the face.

Input

The first line of input will contain an integer NN denoting the number of flaws. 3≤N≤5 0003 \leq N \leq 5\,000

This is followed by NN lines of input, each containing three real numbers in the range −1 000.0…1 000.0-1\,000.0\ldots 1\,000.0, denoting the (x,y,z)(x,y,z) coordinates of a single flaw. Each number will contain at most 66 digits following a decimal point. The decimal point may be omitted if all succeeding digits are zero.

Output

Print the diameter of the smallest drill bit that would remove all the flaws.

The answer is considered correct if the absolute or relative error is less than 10−410^{-4}

Examples3

  1. Example 1

    Input
    3
1.0 0.0 1.4
-1.0 0.0 -1.4
0.0 1.0 -0.2
    Expected output
    2.0000000000

  2. Example 2

    Input
    5
1.4 1.0 0.0
-0.4 -1.0 0.0
-0.1 -0.25 -0.5
-1.2 0.0 0.9
0.2 0.5 0.5
    Expected output
    2.0000000000

  3. Example 3

    Input
    8
435.249 -494.71 -539.356
455.823 -507.454 -539.257
423.394 -520.682 -538.858
446.507 -501.953 -539.37
434.266 -503.664 -560.631
445.059 -549.71 -537.501
449.65 -506.637 -513.778
456.05 -499.715 -561.329
    Expected output
    49.9998293198