26003번 - Lowest Latency 다국어인터랙티브

문제

It is the year 2222. The whole universe has been explored, and settlements have been built on every single planet. You live in one of these settlements. While life is comfortable on almost all aspects, there is one dire problem: the latency on the internet connection with other planets is way too high.

Luckily, you have thought of a solution to solve this problem: you just need to put Bonded, Astronomically Paired Cables between all planets, and internet will be super fast! However, as you start developing this idea, you discover that constructing a cable between two planets is more difficult than expected. For this reason, you would like the first prototype of your cable to be between two planets which are as close as possible to each other.

From your astonomy class, you know that the universe is best modelled as a large cube measuring 10ドル^9$ lightyears in each dimension. There are exactly 10ドル^5$ stationary planets, which are distributed completely randomly through the universe (more precisely: all the coordinates of the planets are independent uniformly random integers ranging from 0ドル$ to 10ドル^9$).

Given the random positions of the planets in the universe, your goal is to find the minimal Euclidean distance between any two planets.

입력

The input consists of:

• One line with an integer $n,ドル the number of planets.
• $n$ lines, each with three integers $x,ドル $y,ドル and $z$ (0ドル \leq x, y, z < 10^9$), the coordinates of one of the planets.

Your submissions will be run on exactly 100ドル$ test cases, all of which will have $n = 10^5$. The samples are smaller and for illustration only.

Each of your submissions will be run on new random test cases.

출력

Output the minimal Euclidean distance between any two of the planets.

Your answer should have an absolute or relative error of at most 10ドル^{-6}$.

제한

힌트