E. Rest In The Shades

题目链接

题解

高档题。题意大概是 x 轴上方有若干个点,x 轴上有若干段互不相交的墙壁, x 轴下有一个光源延 x 轴正方向移动,求每个点被阴影覆盖的时间。
这一题本身没有什么高深的算法数据结构,主要是复杂问题转换成简单问题的思想。 首先注意到数据规模很大,不能直接暴力做。 注意到题目已经简化了很多问题,比如墙在 x 轴上,光源沿 x 方向移动。因此我们设想将点对着光源运动的首末位置投影到 x 轴上,形成一个区间,把原问题转换成 x 轴上区间与墙的重合比例问题。使用类似前缀和的方法在 O(log n) 的复杂度下计算出重合长度与总长度来计算重合比例,乘以运动时间即是被阴影覆盖时间。最终总复杂度为 O(n log n) 。

代码

#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int l[MAXN], r[MAXN], sum[MAXN];
int Sy, a, b, n;
int q, q1, q2;

inline double query(double loc) {
    int pos = lower_bound(l, l + n + 1, loc) - l;
    pos--;
    if (r[pos] <= loc)return sum[pos];
    else return sum[pos] - (r[pos] - loc);
}

int main() {
    scanf("%d %d %d %d", &Sy, &a, &b, &n);
    l[0] = r[0] = -INF;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        sum[i] = sum[i - 1] + r[i] - l[i];
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        scanf("%d %d", &q1, &q2);
        double locl = a + (double)(q1 - a) / (q2 - Sy)*(-Sy);
        double locr = b + (double)(q1 - b) / (q2 - Sy)*(-Sy);
        printf("%.8lf\n", (query(locr) - query(locl)) / (locr - locl)*(b - a));
    }
}

标签: binary search, geometry

添加新评论