zrj2012-B3-0011

从 Trac 迁移的文章

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

原文章内容如下：

题目大意：依次给出若干矩形，每个矩形有一个属性，是0或1，表示擦出或染色。然后给出一个由若干段构成的折线段，问折线段被染色的部分的总长度。
折线段各段之间互不影响，可以分开求。对于每一段线段，我们去和所有矩形求交，得到的部分转化为[l,r]区间的形式（0<=l<=r<=1），再进行离散化，然后可以用o(n^2)暴力染色，能过。
至于求与矩形的交，可以先特判线段与坐标轴平行的情况，对于剩下的，一次与矩形四边求交，然后再整合一下。PS：要注意线段经过矩形顶点，出现3、4个交点的情况。

题目大意：依次给出若干矩形，每个矩形有一个属性，是0或1，表示擦出或染色。然后给出一个由若干段构成的折线段，问折线段被染色的部分的总长度。

折线段各段之间互不影响，可以分开求。对于每一段线段，我们去和所有矩形求交，得到的部分转化为[l,r]区间的形式（0<=l<=r<=1），再进行离散化，然后可以用o(n^2)暴力染色，能过。

至于求与矩形的交，可以先特判线段与坐标轴平行的情况，对于剩下的，一次与矩形四边求交，然后再整合一下。PS：要注意线段经过矩形顶点，出现3、4个交点的情况。