[TYVJ] 2053 穿越七色虹[Nescafé29]

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

在Nescafe27和28中，讲述了一支探险队前往Nescafe之塔探险的故事……

当两位探险队员以最快的时间把礼物放到每个木箱里之后，精灵们变身为一缕缕金带似的光，簇簇光芒使探险队员们睁不开眼睛。待一切平静下来之后，探险队员来到了一座宫殿中，玉制的石椅上坐着两个人……

“你们就是……Nescafe之塔护法中的两位？”

“是的，我们就是神刀护法xlk和飞箭护法riatre……你们来这里做什么？”

“我们是前来拜访圣主和四位护法的……”

“如果你们想见圣主和其它两位护法，你们必须穿过前方的七色彩虹。请随我来吧……”

描述

探险队员们跟随两位护法来到了七色虹前。七色虹，就是平面直角坐标系中赤橙黄绿青蓝紫七个半圆，第i座($$1 \leq i \leq 7$$)半圆形彩虹的圆心是($$x_i,0$$)，半径是$$r_i$$，半圆上所有点的纵坐标均为非负数。探险队员可以看做一条竖直的、长度等于身高的线段，线段的底端纵坐标为0，最高的一位探险队员的身高为$$h$$。

现在探险队员们要从(0,0)穿越七色虹到达($$x_0,0$$)，穿越七色虹的过程中，探险队员的整个身体必须始终在至少一个半圆形彩虹的内部。由于彩虹的半径$$r_i$$可能太小了，不足以满足这个条件，因此两位护法决定帮助他们把所有彩虹的半径都增大一个非负实数$$r$$。探险队员们想知道，$$r$$最小是多少呢？

输入格式

第一行两个实数h、$$x_0$$，表示身高和目的地横坐标。

接下来七行每行两个实数$$x_i$$、$$r_i$$，表示七座半圆形彩虹的圆心和半径。

输出格式

输出最小的$$r$$，四舍五入保留2位小数。

测试样例

输入

4.0 36.0
0.0 4.0
6.0 4.0
12.0 4.0
18.0 4.0
24.0 4.0
30.0 4.0
36.0 4.0

输出

1.00

备注

对于 100% 的数据，满足$$0 \leq x_i,x_0 \leq 10^5$$，$$0 < h < 100$$。

思路

二分

二分枚举增加半径长度

代码

#include <bits/stdc++.h>
using namespace std;

const double esp=1e-7;
struct node
{
    double x,r;
}a[8];
double h,x0;

inline double cal(double r)
{
    return sqrt((pow(r,2)-pow(h,2)));
}

bool judge(double x)
{
    bool s[8];
    memset(s,1,sizeof(s));
    double l[8],r[8];
    double L=0,R=x0;
    int cnt=0;
    for(int i=1;i<=7;i++)
    {
        double j=cal(a[i].r+x);
        double left=a[i].x-j;
        double right=a[i].x+j;
        if(left<L && right<L || left>R && right>R)    continue;
        else if(left<L && right>L)    L=right;
        else if(left<R && right>R)    R=left;
        else if(left>=L && right<=R)    l[++cnt]=left,r[cnt]=right;
        if(L>R)    return 1; 
    }
    double s1=l[1],s2=r[1];
    s[1]=0;
    for(int i=1;i<cnt;i++)
        for(int j=1;j<=cnt;j++)
            if(s[j])
            {
                if(l[j]<=s2 && r[j]>=s2)
                {
                    s[j]=0;
                    s2=r[j];
                    break;
                }
                if(r[j]>=s1 && l[j]<=s1)
                {
                    s[j]=0;
                    s1=l[j];
                    break;
                }
                if(r[j]>=s2 && l[j]<=s1)
                {
                    s[j]=0;
                    s1=l[j];
                    s2=r[j];
                    break;
                }
                if(l[j]>=s1 && r[j]<=s2)
                {
                    s[j]=0;
                    break;
                }
            }
    if(s1<=L && s2>=R)    return 1;
    else return 0;
}

int main()
{
    cin>>h>>x0;
    double l=0,r=20000;
    for(int i=1;i<=7;i++)
    {
        cin>>a[i].x>>a[i].r;
    }
    while(r>=l+esp)
    {
        double mid=(l+r)/2;
        if(judge(mid))    r=mid;
        else    l=mid;
    }
    printf("%.2lf\n",l);
}