第十五届浙江大学宁波理工学院程序设计大赛 F. Pylon Link(二分+图连通)

题目链接：https://ac.nowcoder.com/acm/contest/303/F

       要求一个最小的r使得所有的塔连通，所以我们就去二分半径r，然后用bfs去判断图是否连通就好了。

AC代码：

#include <bits/stdc++.h>
#define maxn 505
#define ll long long
using namespace std;
int T;
int n;
ll x[maxn],y[maxn];
ll pre[maxn][maxn];
bool vis[maxn];
  
ll dist(ll x1,ll y1,ll x,ll y){
    double ans = sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
    return ceil(ans);
}
  
bool Check(ll r){
    memset(vis,false,sizeof(vis));
    queue<int> q;
    q.push(1);
    vis[1] = true;
    int ans = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(ans == n - 1)return true;
        for(int i=1;i<=n;i++){
            if(i == u) continue;
            if(vis[i] == false && pre[u][i] <= 2.0 * r){
                vis[i] = true;
                ans ++;
                q.push(i);
            }
        }
    }
    return false;
}
  
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&x[i],&y[i]);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                pre[i][j] = dist(x[i], y[i], x[j], y[j]);
                // Max = max(Max, pre[i][j]);
            }
        }
        ll l = 0, r = 2e18, mid;
        while(l < r){
            mid = (l + r) >> 1;
            if(Check(mid)){
                r = mid;
            }
            else l = mid + 1;
        }
        printf("%lld\n", r);
    }
    return 0;
}