1 条题解
-
0
解题思路:
题目要求我们计算点光源在 轴上形成的亮区数量。亮区是指没有被任何线段阴影覆盖的区域。我们需要根据给定的光源位置和线段信息,计算这些阴影在 轴上的投影,并统计未被阴影覆盖的区间数量。
关键步骤:
阴影投影计算:
每条线段在 轴上的阴影是其两个端点在光源照射下的投影点形成的区间。
投影点的 坐标可以通过相似三角形原理计算:对于端点 ,其投影点 。
区间合并:
将所有线段的阴影区间按照左端点排序。
遍历排序后的区间,合并重叠或相邻的区间,得到不重叠的阴影区间集合。
亮区计算:
阴影区间将 轴划分为多个暗区和亮区。亮区的数量等于阴影区间的数量加 (因为阴影区间之间的间隙就是亮区)。
如果没有线段,则整个 轴都是亮区,输出 。
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
- 上传者