tkdsheep-solution-0011

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
prowindy学长的神题，这种类型的题是我的软肋，珍惜吧，做一道就进步一点

参考了多位学长的解题报告，大致就是单独计算每条线段的最终答案

对于一条线段，按顺序与这些矩形求交（注意一定要按顺序来，因为是擦除和涂色操作）

每次求交都得到一个区间(x1,x2)，表示线段上相交的区间，可以参照zyc学长所说的对区间进行归一化

就是按照比例转化成0~1的区间

如果求线段与矩形相交的区间？

分两步，先计算矩形的两条水平线与线段的交点，得到区间(x1,x2)，再用矩形的两条竖线更新这个区间

注意线段如果是竖直的，需要特判

总之分类讨论的地方比较多，要自己多画图仔细想一下，不要有遗漏

这样很多个区间求出来之后，再【按顺序】做线段的合并、删除等操作，题目数据卡得不是很严，可以用map先把所有线段的端点保存起来

然后每次染色、擦除直接对map里的点扫描即可
}}}

prowindy学长的神题，这种类型的题是我的软肋，珍惜吧，做一道就进步一点
参考了多位学长的解题报告，大致就是单独计算每条线段的最终答案
对于一条线段，按顺序与这些矩形求交（注意一定要按顺序来，因为是擦除和涂色操作）
每次求交都得到一个区间(x1,x2)，表示线段上相交的区间，可以参照zyc学长所说的对区间进行归一化
就是按照比例转化成0~1的区间
如果求线段与矩形相交的区间？
分两步，先计算矩形的两条水平线与线段的交点，得到区间(x1,x2)，再用矩形的两条竖线更新这个区间
注意线段如果是竖直的，需要特判
总之分类讨论的地方比较多，要自己多画图仔细想一下，不要有遗漏
这样很多个区间求出来之后，再【按顺序】做线段的合并、删除等操作，题目数据卡得不是很严，可以用map先把所有线段的端点保存起来
然后每次染色、擦除直接对map里的点扫描即可