本蒟蒻过的第二道黑题一道不太吓人的计算几何。

本题所要求的激光束能照射到的挡板长度之和显然由若干小线段组成，因为这些小线段是由挡板在导轨上的投影产生的，为方便计算，可以先将坐标系进行旋转，使导轨成为 $x$ 轴。

根据解析几何知识，点 $(x,y)$ 绕原点逆时针旋转 $\theta$ 后的坐标为：

令导轨上一点 $(x_1,y_1)$ 为新坐标系的原点，即将挡板端点平移 $(-x_1,-y_1)$，再用上述公式计算逆时针旋转 $\theta=-\arctan\frac{y_2-y_1}{x_2-x_1}$ 后的新坐标即可。

得到新坐标后，所有挡板在导轨上的投影被端点的横坐标切成了最多 $(2n-1)$ 段，每一段对答案的贡献即为导轨两侧可见挡板与导轨夹角的余割值之和与这一段的水平宽度的乘积。

如何维护导轨两侧最近的挡板？由于挡板不交叉，一个挡板与其他挡板的相对上下位置是固定的，这就意味着我们可以通过比较任一横坐标时的纵坐标来判断两个挡板中哪个相对在前。因此可以使用扫描线配合基于比较来维护最值且支持删除的数据结构，如平衡树、可删除堆等。使用 std::set 在本题中是个不错的选择。

处理出每段中导轨两侧可见挡板与导轨夹角的余割值之和之后，用双指针来统计答案即可。容易证明最优区间（若有无穷多最优区间则取端点）的两端点中至少有一个为某一挡板端点的横坐标，最方便的写法便是向左对齐扫一遍，向右对齐再扫一遍，这样就不会涉及太多繁琐的细节了。

更多细节详见代码中的注释~

#include <bits/stdc++.h>

double t;
struct Seg { // 存储挡板所在的直线一次函数，代入 x 比较 y
    double k, b, v;
    Seg(const std::array<double, 4> &s) {
        double dx = s[2] - s[0], dy = s[3] - s[1];
        k = dy / dx, b = s[1] - k * s[0], v = hypot(dx, dy) / std::abs(dx);
    }
    friend bool operator<(Seg x, Seg y) { return x.k * t + x.b < y.k * t + y.b; }
};

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::array<double, 4>> v(n);
    for (auto &s : v)
        for (auto &x : s)
            std::cin >> x;

    // 变换坐标系
    double Ax, Ay, Bx, By, L;
    std::cin >> Ax >> Ay >> Bx >> By >> L;
    double th = -atan2(By - Ay, Bx - Ax), si = sin(th), co = cos(th); // 预计算旋转角的三角函数值
    for (auto &[ax, ay, bx, by] : v) {
        ax -= Ax, ay -= Ay, bx -= Ax, by -= Ay; // 平移原点
        std::tie(ax, ay, bx, by) = std::make_tuple(ax * co - ay * si, ax * si + ay * co, bx * co - by * si, bx * si + by * co);
    }

    // 添加事件
    std::vector<std::tuple<double, bool, int>> evt;
    for (int i = 0; i < n; i++) { // 事件中的 bool 值 op 为 true 表示插入，false 表示删除
        evt.emplace_back(v[i][0], v[i][0] < v[i][2], i);
        evt.emplace_back(v[i][2], v[i][2] < v[i][0], i);
    }
    std::sort(evt.begin(), evt.end());

    // 扫描线
    std::set<Seg> now[2];               // now[0] 存储 y 坐标为正的挡板，now[1] 存储 y 坐标为负的挡板
    std::vector<double> res(n * 2 + 1); // res[i] 表示 evt[i-1] 到 evt[i] 之间导轨两侧可见挡板与导轨夹角的余割值之和
    for (int i = 0; i < n * 2; i++) {
        bool op;
        int id;
        std::tie(t, op, id) = evt[i];
        if (op)
            now[v[id][1] < 0].emplace(Seg(v[id])); // 插入
        else
            now[v[id][1] < 0].erase(Seg(v[id])); // 删除
        if (!now[0].empty())
            res[i + 1] += now[0].begin()->v; // y 坐标为正
        if (!now[1].empty())
            res[i + 1] += now[1].rbegin()->v; // y 坐标为负
    }

    // 双指针统计答案
    double sum = 0, ans = 0;
    auto gx = [&](const int &i) { return std::get<0>(evt[i]); }; // 获取事件的 x 坐标
    // 从左到右，统计左端点与事件对齐的区间
    for (int l = 0, r = 0; r + 1 < n * 2; sum -= res[l + 1] * (gx(l + 1) - gx(l)), l++) {
        for (; r + 1 < n * 2 && gx(r + 1) <= gx(l) + L; r++)
            sum += res[r + 1] * (gx(r + 1) - gx(r));
        ans = std::max(ans, sum + (gx(l) + L - gx(r)) * res[r + 1]);
    }
    sum = 0;
    // 从右到左，统计右端点与事件对齐的区间
    for (int l = n * 2 - 1, r = l; l; sum -= res[r] * (gx(r) - gx(r - 1)), r--) {
        for (; l && gx(l - 1) >= gx(r) - L; l--)
            sum += res[l] * (gx(l) - gx(l - 1));
        ans = std::max(ans, sum + (gx(l) + L - gx(r)) * res[l]);
    }

    // 搞定，输出！
    std::cout << std::fixed << std::setprecision(15) << ans << std::endl;
}

int main() {
    int T;
    std::cin >> T;
    while (T--)
        solve();
    return 0;
}

通过许多卡常手段把总时间卡到了 703ms……时限 10s 是认真的吗