题解：P7249 [BalticOI 2012 Day1] 移动网络

qwertyuiop12345679 · 2024-12-01 12:49:31 · 题解

直接上代码

#include <bits/stdc++.h>
using namespace std;
int n,l,a[1000005],b[1000005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool check(double len)
{
    double now=0;
    for(int i=1;i<=n;i++)
    {
        double dis=sqrt(len*len-1.0*b[i]*b[i]);
        double lft=a[i]-dis,rht=a[i]+dis;
        if(lft<=now&&now<=rht)now=rht;
    }
    return now>=l;
}
int main()
{
    n=read(),l=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=read();
    double l=0,r=1414213562.374,mid;
    while(r-l>=0.0003) 
    {
        mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    printf("%.5lf",l);
    return 0;
}