MENU

COGS1247/Tyvj2053 [Nescafé29]穿越七色虹

COGS1247

Tyvj2053

二分,使用勾股定理计算每个彩虹内合法的区间,转为区间覆盖问题。

#include<cstdio>
#include<algorithm>
#include<cmath>
double h, x0, h2;
struct node { double x, r; }rb[7], temp[7];
inline bool operator<(const node &a, const node &b) { return a.x < b.x; }
int judge(double x) {
    for(int i = 0; i < 7; ++i)if(x + rb[i].r >= h) {
        double t = rb[i].r + x, dis = sqrt(t * t - h2), cur = rb[i].x;
        temp[i].x = cur - dis, temp[i].r = cur + dis;
    }
    std::sort(temp, temp + 7);
    double end = 0;
    for(int i = 0; i < 7; ++i) {
        if(end > x0)return 1;
        if(end < temp[i].x)return 0;
        end = std::max(end, temp[i].r);
    }
    return end >= x0 ? 1 : 0;
}
int main() {
    scanf("%lf%lf", &h, &x0), h2 = h * h;
    for(int i = 0; i < 7; ++i)scanf("%lf%lf", &rb[i].x, &rb[i].r);
    double l = 0, r = 10000, mid;
    while(r - l >= 1e-3)judge(mid = (l + r) / 2) ? r = mid : l = mid;
    printf("%.2f", l);
}
Leave a Comment

captcha
请输入验证码