https://www.luogu.com.cn/problem/P1783
有点像 https://www.luogu.com.cn/problem/P3958

并查集

本质上就是让海滩的左边界和右边界连接起来

一共m个点，可以再假设有两个虚拟点，分别是左边界和右边界

先预处理，求出m个点，任意两点两两相连的边的距离，以及这m个点连左边界和右边界的边的距离

然后将这些边按距离从小到大排序，依次连边，每次检查一下左右边界是否连接。
注意，求距离时，如果是点到边界的距离，需要乘以2。
因为两个防御塔之间要连接的话，只需要一半的攻击距离，要除以2
而如果是防御塔和边界之间连接，则需要完整的攻击距离。
为了方便代码实现，可以直接让点连边界的距离直接乘以2，这样最后统一除以2

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, m, cnt; // cnt:边的数量 
int x[1010], y[1010], fa[1010];
struct Edge
{
  int x, y; // 边(x, y)
  double dis;
} edge[N];
double dis(int x1, int y1, int x2, int y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
bool cmp(Edge a, Edge b) {
  return a.dis < b.dis;
}
int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
  {
    cin >> x[i] >> y[i];
    fa[i] = i;
  }
  // 将m个点两两连边
  for (int i = 1; i < m; i++)
    for (int j = i + 1; j <= m; j++) {
      edge[++cnt] = {i, j, dis(x[i], y[i], x[j], y[j])};
    }
  // 再将m个点和左右边界连边
  /*
    因为最后要统一拿边的距离除以2
    因为两个防御塔之间要连接只需要一半距离的攻击范围即可
    但是防御塔和边界间就只能靠防御塔自己一个 所以这里先把距离乘以2 最后答案再除以2也不会影响
    防御塔和边界间连边的这种情况
  */
  for (int i = 1; i <= m; i++)
  {
    edge[++cnt] = {i, 0, x[i] * 2.0};
    edge[++cnt] = {i, m + 1, (n - x[i]) * 2.0};
  }
  sort(edge + 1, edge + cnt + 1, cmp);
  fa[0] = 0, fa[m + 1] = m + 1; // 0和m+1是虚拟的两个点 0是左边界 m+1是右边界
  int ans = 0;
  for (int i = 1; i <= cnt; i++)
  {
    int x = edge[i].x, y = edge[i].y;
    int rx = find(x), ry = find(y);
    if (rx != ry)
      fa[rx] = ry;
    if (find(0) == find(m + 1)) {
      ans = i;
      break;
    }
  }
  cout << fixed << setprecision(2) << edge[ans].dis / 2.0;





  return 0;
}