P1783 海滩防御

题目描述

WLP同学最近迷上了一款网络联机对战游戏（终于知道为毛JOHNKRAM每天刷洛谷效率那么低了），但是他却为了这个游戏很苦恼，因为他在海边的造船厂和仓库总是被敌方派人偷袭。于是，WLP动用了他那丰满且充实的大脑（或许更偏向前者），想出了一个好主意，他把海滩分成垂直于海岸线的若干列，在其中的几列上放置几个信号塔，试图来监视整个海滩。然而，WLP是一个非常心急的人，他把信号塔建好后才发现还需给信号塔供能，它们才能投入使用（这不是废话么），它们都有一个工作半径，一个圆形区域里的所有敌人都逃不过它们的监视，不过，WLP发现，敌人们非常狡猾，除非他将道路完全封死，否则WLP的敌人可以走过一条任意弯曲的路（不一定走整点，但是不会出第0列和第N列构成的边界）来偷他的东西。

于是，WLP就思考了：到底需要给每个信号塔多大的工作半径，才能将从海滩到内地的路径完全封死呢？他再次动用了他那丰满且充实的大脑，想了一堂数学课，终于，还是没想出来。于是，他向LZZ神犇求助（额……C_SUNSHINE的身份是不是暴露了）。

终于，在WLP：“%^!*@#!*(*!*#@$^&（此处省略无数卖萌场景）”的哀求下，LZZ神犇写了一个程序，在1s内就解决了问题。但是，邪恶的LZZ神犇决定要将这个难题共享给无数无辜的OIer，所以，现在轮到你了。

输入输出格式

输入格式：

第一行两个整数N和M：表示海滩被WLP分成的列数0-N和信号塔个数。

第2-M+1行：每行两个数Xi，Yi表示1-M号信号塔所在的列数和离开海滩的距离。

输出格式：

一行一个实数，表示最小的工作半径，保留两位小数。

说明

对于10%的数据：1≤M≤10，1≤Yi≤100;

对于30%的数据：1≤M≤50，1≤Yi≤1,000;

对于80%的数据：1≤M≤500，1≤Yi≤1,000;

对于100%的数据：1≤M≤800，1≤N≤1000，1≤Xi≤N，1≤Yi≤100,000.

---

和2017提高组D2T1有点像，只是外面套了个二分答案的壳子

二分半径+并查集维护边界是否连通

---

Code：

#include <cstdio>

#include <cmath>

#include <iostream>

using namespace std;

const int N=1010;

const double eps=1e-4;

pair <double ,double > loc[N];

int n,m;//列数和信号塔个数

int f[N];

double get(double x1,double y1,double x2,double y2)

{

    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

int find(int x)

{

    return f[x]=x==f[x]?x:find(f[x]);

}

void merge(int x,int y)//把y合并到x上

{

    f[find(y)]=find(x);

}

bool check(double r)

{

    for(int i=1;i<=m;i++)

    {

        f[i]=i;

        if(loc[i].first-r<=0) f[i]=0;

        if(loc[i].first+r>=n) f[i]=n+1;

    }

    f[0]=0,f[n+1]=n+1;

    for(int i=1;i<=m;i++)

        for(int j=i+1;j<=m;j++)

            if(get(loc[i].first,loc[i].second,loc[j].first,loc[j].second)<=2*r)

                merge(i,j);

    return find(n+1)==find(0);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

        scanf("%lf%lf",&loc[i].first,&loc[i].second);

    double l=0,r=n;

    while(l+eps<r)

    {

        double mid=(l+r)/2.0;

        if(check(mid))

            r=mid;

        else

            l=mid;

    }

    printf("%.2lf\n",l);

    return 0;

}

---

2018.7.11