2012-0011

从 Trac 迁移的文章

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

原文章内容如下：

这题本质是涂色点集S和那根线上点集L的交。
而S集合是由若干个可能相交的点集聚成：S = A1 ∪ A2 ∪ A3 ∪ ...
很容易想到的是把S割成互不相交的子集，然后分别和L求交，最后答案累加即可。
所以很自然地可以想到矩形切割，但是这里有一个很严重的问题，矩形切割切出来的矩形其实并不是没有交集的，他们在矩形的边缘那条线上会出现重叠。这样子就坑爹了，这里大概还是把边缘拿出来单独离散化处理比较好...总之是有点复杂了
这样子的思路本质是求了S，再求S ∩ L
zYc学长们的策略其实是求(A1∩L)∪(A2∩L)∪(A3∩L)∪...
这样子就只用求出一个矩形在线段上的覆盖部分，然后对若干个线段求并什么的就好了。
设线段两个点为p,q，那么q-p这个向量可伸缩的范围就是0~1之间...矩形在线段上的覆盖部分，就可以用一个0.0~1.0的区间表示。然后最后对这些区间求并就可以了。
by edward_mj

这题本质是涂色点集S和那根线上点集L的交。

而S集合是由若干个可能相交的点集聚成：S = A1 ∪ A2 ∪ A3 ∪ ...

很容易想到的是把S割成互不相交的子集，然后分别和L求交，最后答案累加即可。

所以很自然地可以想到矩形切割，但是这里有一个很严重的问题，矩形切割切出来的矩形其实并不是没有交集的，他们在矩形的边缘那条线上会出现重叠。这样子就坑爹了，这里大概还是把边缘拿出来单独离散化处理比较好...总之是有点复杂了

这样子的思路本质是求了S，再求S ∩ L

zYc学长们的策略其实是求(A1∩L)∪(A2∩L)∪(A3∩L)∪...

这样子就只用求出一个矩形在线段上的覆盖部分，然后对若干个线段求并什么的就好了。

设线段两个点为p,q，那么q-p这个向量可伸缩的范围就是0~1之间...矩形在线段上的覆盖部分，就可以用一个0.0~1.0的区间表示。然后最后对这些区间求并就可以了。

by edward_mj