#### Nếu bạn đã **thử suy nghĩ** mà vẫn chưa có hướng đi phù hợp thì có thể tham khảo một vài gợi ý sau nhé.
## Gợi ý:
1. Xem các toạ độ $(x_i, y_i)$ như là các đỉnh trong một đồ thị.
2. Khoảng cách giữa 2 điểm $(x_i, y_i)$ và $(x_j, y_j)$, $(i \neq j)$ được tính bằng công thức
Euclid: $dist(i, j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$.
3. Tính trước và lưu khoảng cách của đỉnh $i$ với $n-1$ đỉnh còn lại.
4. Chặt nhị phân.
## Lời giải:
**Lưu ý:** Lời giải bên dưới có sử dụng các **hàm lambda** cũng như từ khoá **auto**,
nếu bạn tham gia các kỳ thi về học thuật như HSGTP, HSGQG,... thì không nên sử dụng để tránh bị 0đ nhé <3
**ĐPT: $O(N * log_2N)$**
Code: [link](https://ideone.com/03Qst0).
```cpp
/**
* author: anhtri
* created: 11.08.2024 19:01:52
**/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pow(n) (1LL * (n) * (n))
#define pii pair<int, int>
#define fi first
#define se second
const int N = 1e3 + 4;
vector<int> adj[N];
pii p[N];
ll dist[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i].fi >> p[i].se;
auto cost = [&](int x, int y) -> double {
return pow(p[x].fi - p[y].fi) + pow(p[x].se - p[y].se);
};
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n - 1; i++) {
for (int j = i + 1; j <= n; j++) {
adj[i].push_back(j);
adj[j].push_back(i);
dist[i][j] = dist[j][i] = cost(i, j);
}
}
auto good = [&](double r) {
r = pow(r * 2);
queue<int> q;
q.push(1);
vector<bool> vis(n + 4);
vis[1] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int &v : adj[u]) {
if (vis[v] || dist[u][v] > r) continue;
vis[v] = true;
q.push(v);
}
}
for (int i = 1; i <= n; i++)
if (vis[i] == false) return false;
return true;
};
double l = 0, r = 1e9 + 4;
for (int i = 1; i <= 60; i++) {
double m = (l + r) / 2;
if (good(m)) r = m;
else l = m;
}
cout << fixed << setprecision(6) << r;
cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
return 0;
}
```
anhtri
Created at
1 likes