并查集 + 二分
我是 并查集 + 二分 做的QVQ
思路：两两枚举点之间的距离，sort排序，使距离有序。二分答案，每次判断是否符合条件，然后缩小查询范围，直到满足题目要求（保留2位小数精度就为 0.001就好了）最后保留两位小数输出
核心 判断是否符合条件：
对于每次判断，首先应初始化并查集。因为距离有序，一直并集直到两点距离大于（要判断的）k的两倍（k为每次二分检查的半径，两点距离大于半径即两点相离）为止。
（现在所有距离小于k*2 都被联通了）两两枚举所有点，若有一点i离左海岸线的距离<k，说明点i在半径为k的条件下能够到左边界；同理，若有一点j离右海岸线的距离 + k > len说明点j在半径为k的条件下够得到右边界，如果i，j在同一集合内，说明成立（左边界->i->j->右边界；满足封锁）
需要注意的是：
并查集初始化需从0开始（读题）；
每次判断成立都要初始化并查集；
代码如下（注释并上）：
#include<iostream>#include<algorithm>#include<cmath>#include<cstdio>using namespace std;const int maxn = 1001100;int num,nr;//点数，边数int len;//海滩宽度int father[maxn];//并查集struct R{int u,v;double dis;}I[maxn];//边struct Node{int x,y;}N[maxn];//点bool cmp(R a,R b){return a.dis < b.dis;//sort的cmp函数}int findfather(int v){//查找祖先（注意压缩路径【不然也许会超时QAQ】）if(father[v] == v)return v;int F = findfather(father[v]);father[v] = F;return F;}void Union(int a,int b){//并集int faA = findfather(a);int faB = findfather(b);if(faA != faB){father[faA] = faB;}}bool check(double k){//判断函数for(int i = 0;i < num;i++)father[i] = i;//并查集每次初始化int i = 1;while(I[i].dis <= 2 * k && i <= nr){//在当前k下能连通的全部连通Union(I[i].u,I[i].v);i++;}for(int i = 0;i < num;i++){//两两枚举for(int j = 0;j < num;j++){if(findfather(i) == findfather(j) && N[i].x - k < 0 && N[j].x + k > len){ return 1;}}}return 0;}double search(double l,double r){while(l + 0.001 < r){//二分，精度为0.001double mid = (l + r)/2;if(check(mid)){//成立就缩小上界r = mid;}else{l = mid;}}return r;}int main(){cin>>len>>num;//输入宽度和点数for(int i = 0;i < num;i++)father[i] = i;//并查集初始化for(int i = 0;i < num;i++){cin>>N[i].x>>N[i].y;//输入点坐标}for(int i = 0;i < num;i++){//两两枚举，计算点与点之间的距离for(int j = i;j < num;j++){I[++nr].u = i;I[nr].v = j;I[nr].dis =sqrt (1.0 * (N[i].x - N[j].x) * (N[i].x - N[j].x) + (N[i].y - N[j].y) * (N[i].y - N[j].y));//记得加math头文件}}sort(I + 1,I + nr + 1,cmp);//按距离从小到大排序printf("%.2f\n",search(0.0,10000000.0) );//输出return 0;}
End.(求过)