시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 (추가 시간 없음) 1024 MB84443452.308%

문제

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}$.

예제 입력 1

5
10 5 1
8 2 0
4 7 5
1 0 9
0 10 7

예제 출력 1

3.7416573867739413

예제 입력 2

3
790726336 656087587 188785845
976472310 22830435 160538063
211966015 87530388 542618498

예제 출력 2

660540781.9387681

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2022 L번

  • 문제를 만든 사람: Reinier Schmiermann

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.