#### 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;
}
```
Cách này mình dùng cây khung nhỏ nhất nhưng đang ở phần bfs/dfs nên khuyên các bạn chỉ nên tham khảo
sơ qua cách này thôi để có 1 hướng giải khác cho bài toán. Về thuật toán :
Ban đầu mình sẽ duyệt để lấy tất cả khoảng cách các cạnh nối giữa 2 ra đa sau đó lưu vào 1 vector.
Sau đó mình sort lại và thực hiện thuật cây khung nhỏ nhất .
Thuật toán cây khung về cơ bản sẽ tạo ra 1 cây nối n đỉnh với nhau sao cho tổng trọng số các cạnh là
nhỏ nhất có thể -> dựa vào đó ta có thể lấy được giá trị tối thiểu để các ra-đa có thể kết nối với
nhau. Chính là cạnh lớn nhất của cây khung.
``` cpp
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pll pair<ll,ll>
const int N=1e3;
using namespace std;
ll n;
pll z[N+3];
vector<pair<ll,pll>>v;
ll cal(pll x,pll y)
{
ll a=abs(x.fi-y.fi);
ll b=abs(x.se-y.se);
return a*a+b*b;
}
void input()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>z[i].fi>>z[i].se;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
ll cc=cal(z[i],z[j]);
v.push_back({cc,{i,j}});
}
}
sort(all(v));
}
ll p[N+3];
ll Find_set(ll u)
{
if(p[u]<0)return u;
return p[u]=Find_set(p[u]);
}
bool Union(ll x,ll y)
{
x=Find_set(x);
y=Find_set(y);
if(x==y)return 0;
if(p[x]>p[y])swap(x,y);
p[x]+=p[y];
p[y]=x;
return 1;
}
void solve()
{
for(int i=1;i<=n;i++)
p[i]=-1;
ll ans=0;
for(auto x : v)
{
if(Union(x.se.fi,x.se.se))
{
ans=max(ans,x.fi);
}
}
cout<<fixed<<setprecision(6)<<(double)sqrt((double)ans)/2;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
#define orz "mo"
if(fopen(orz".inp","r"))
{
freopen(orz".inp","r",stdin);
freopen(orz".out","w",stdout);
}
int t=1;
//cin>>t;
while(t--)
{
input();
solve();
}
cerr<< "\nTime elapsed: "<< 1.0*clock()/CLOCKS_PER_SEC<<"s";
return 0;
}
```
anhtri
Created at
25 likes
Raiden_Ei
Created at
0 likes