1 条题解

  • 0
    @ 2025-6-17 18:48:56

    解题思路:

    题目要求我们计算点光源在 xx 轴上形成的亮区数量。亮区是指没有被任何线段阴影覆盖的区域。我们需要根据给定的光源位置和线段信息,计算这些阴影在 xx 轴上的投影,并统计未被阴影覆盖的区间数量。

    关键步骤:

    阴影投影计算:

    每条线段在 xx 轴上的阴影是其两个端点在光源照射下的投影点形成的区间。

    投影点的 xx 坐标可以通过相似三角形原理计算:对于端点 (x,y)(x, y),其投影点 x=xL(yL(xLx))/(yLy)x' = xL - (yL * (xL - x)) / (yL - y)

    区间合并:

    将所有线段的阴影区间按照左端点排序。

    遍历排序后的区间,合并重叠或相邻的区间,得到不重叠的阴影区间集合。

    亮区计算:

    阴影区间将 xx 轴划分为多个暗区和亮区。亮区的数量等于阴影区间的数量加 11(因为阴影区间之间的间隙就是亮区)。

    如果没有线段n=0(n = 0),则整个 xx 轴都是亮区,输出 11

    C++实现:

    #include <stdio.h>
    #include <algorithm>
    using std::sort;
    using std::swap;
    
    double X, Y; // 光源的坐标 (X, Y)
    
    // 结构体表示阴影区间
    struct Node {
        double left, right; // 区间的左右端点
    } arr[102]; // 最多100条线段,数组大小设为102
    
    // 计算端点在光源照射下的投影点x坐标
    double getX(double a, double b) {
        return X - Y * (X - a) / (Y - b);
    }
    
    // 比较函数,用于区间排序
    bool cmp(Node a, Node b) {
        return a.left < b.left;
    }
    
    int main() {
        double x1, y1, x2, y2, flag;
        int t, n, ans;
        scanf("%d", &t); // 读取测试用例数量
        while (t--) {
            scanf("%d", &n); // 读取线段数量
            scanf("%lf%lf", &X, &Y); // 读取光源坐标
    
            for (int i = 0; i < n; ++i) {
                scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); // 读取线段端点
                // 计算两个端点的投影点x坐标
                arr[i].left = getX(x1, y1);
                arr[i].right = getX(x2, y2);
                // 确保left <= right
                if (arr[i].left > arr[i].right) swap(arr[i].left, arr[i].right);
            }
    
            // 按照左端点排序
            sort(arr, arr + n, cmp);
    
            ans = 1; // 初始亮区数量为1(如果没有线段)
            if (n == 0) {
                printf("1\n");
                continue;
            }
    
            flag = arr[0].right; // 当前阴影区间的右端点
            for (int i = 1; i < n; ++i) {
                if (flag < arr[i].left) {
                    // 当前区间与前一区间不重叠,亮区数量加1
                    ++ans;
                    flag = arr[i].right;
                } else if (flag < arr[i].right) {
                    // 当前区间与前一区间重叠,更新右端点
                    flag = arr[i].right;
                }
            }
            // 亮区数量 = 阴影区间数量 + 1
            printf("%d\n", ans + 1);
        }
        return 0;
    }
    
    • 1

    信息

    ID
    2463
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    3
    已通过
    1
    上传者