백준 26003 (C++) Lowest Latency

최초 업로드: 2025-09-26 15:31:41

최근 수정 시간: 2025-09-26 16:02:20

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] Lowest Latency

[문제 링크](https://www.acmicpc.net/problem/26003)

## 문제 설명

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:

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

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

## 풀이
먼저 좌표가 $10^9 * 10^9 * 10^9$ 공간에 랜덤하게 $10^5$개가 배치된다. 랜덤성을 이용하여 $10^7 * 10^7 * 10^7$ 크기의 박스 100 * 100 * 100개에 각 좌표를 나눠 담았다. 이러면 한 박스에는 대략 $10^5 / (10^{9 * 3} / 10^{7 * 3}) = 0.1$개씩 담긴다. 문제에서 최대 거리가 $10^6$이라 명시해 놓았기에 임의의 한 박스 안에서의 거리, 임의의 한 박스와 붙어있는 주변 박스와의 거리 중 최소를 계산해주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
const ll border = 1e7;

struct element {
    ll x, y, z;
};

int dx[] = {1, 1, 1, 1, 0, 0, 0};
int dy[] = {1, 1, 0, 0, 1, 1, 0};
int dz[] = {1, 0, 1, 0, 1, 0, 1};

vector<vector<vector<vector<element>>>> board(101, vector<vector<vector<element>>>(101, vector<vector<element>>(101)));

ld minDist = 1e16;

void chkDist(element a, element b) {
    minDist = min(minDist, sqrtl((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z)));
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    while(n--) {
        ll x, y, z; cin >> x >> y >> z;
        board[x/border][y/border][z/border].push_back({x, y, z});
    }

for(int i=0;i<100;i++) {
 for(int j=0;j<100;j++) {
 for(int k=0;k<100;k++) {
 for(int l=0;l<board[i][j][k].size();l++) for(int m=l+1;m<board[i][j][k].size();m++) chkDist(board[i][j][k][l], board[i][j][k][m]);
 for(int cnt=0;cnt<7;cnt++) {
 int nx = i+dx[cnt];
 int ny = j+dy[cnt];
 int nz = k+dz[cnt];
 for(int l=0;l<board[i][j][k].size();l++) for(int m=0;m<board[nx][ny][nz].size();m++) chkDist(board[i][j][k][l], board[nx][ny][nz][m]);
 }
 }
 }
 }
 cout << fixed << setprecision(6) << minDist;
}
```