集训队一次作业题解qpoint.pdfVIP

QPOINT题解

长春吉大附中实验学校

November10,2015

1题目大意

在二维平面上，给定n个两两之间没有交点的简单多边形，有q个询问，每次

给定一个点，要求判断这个点在哪个简单多边形中，或者判断这个点不在任何

一个多边形中。

要求强制。

555

数据范围n≤10，所有多边形的总点数3≤k≤3×10，q≤10。

2算法讨论

2.1算法1

考虑如何判定一个点是否在一个简单多边形中。

令多边形上有k个点，我们可以利用射或者转角法做到O(k)。

对于每组询问，我们都利用这两种方法之一来判定，时间复杂度O(qk)。

2.2算法2

对于只有凸多边形的情况，我们可以利用更加快速的方法来判定一个点是否在

这个凸多边形中。

我们选定一个在凸多边形的点p，并凸多边形上所有点关于点p的极

角序。

那么对于询问点，我们找到询问点以点p为原点的极角，并在极角序中找到这

个极角的前驱、后继点x,y，那么我们能够发现若询问点能够在凸多边形，

必定有询问点在三角形pxy中。反之一定不在。

这样我们只需要O(1)判定一个点在不在一个三角形中就行了。

于是我们O(logk)就能知道一个点在不在凸多边形中。

因此如果都是凸多边形，时间复杂度就能做到O(qnlogk)。

但可惜的是，这个方法显然不能对凹多边形适用；而如果将这个凸多边形拆分

成三角形处理也是没有意义的。

1

2.3算法3

扫描线是处理计算几何问题的一种有效算法。

我们对于每个不同的横坐标做一条垂直于x轴的垂线。

我们可以发现，无论多边形凸凹与否，在两条相邻的垂线之间，都会有一些只

可能在左右两端才相交的线段，这些线段的依据上下的位置关系构成了一个有

序序列。

令两条相邻的垂线的横坐标分别为l,r，则在两条垂线中间夹着的线段我们可以

用x=l+r时的纵坐标值的大小作为顺序。

2

我们只考虑原多边形的横坐标增大的线段，并记录这个线段下面的区域的编号，

如果是某个多边形的区域，则编号为这个多边形的编号；否则编号为空区

域。

对于询问(x,y)，我们只需二分找到x在哪两条相邻垂线之间，然后再在这个

对应的线段序列中找到横坐标等于x时的纵坐标≥y且纵坐标最小的线段（其

实也就是后继），直接看看这条线段下面的区域是什么就行了。

现在我们只要知道怎么这些线段就行了。

如果允许离线，那我们可以将所有的询问按照横坐标从小到大排序，同时用一

颗平衡树所有的线段：我们对于每条线段处理出出现时间和时间，依

次处理每两条相邻垂线之间的线段，在出现时间将对应的线段平衡树，在

删除时间将对应的线段从平衡树中删除，这样每条线段只会被增删各一次，时

间复杂度O(klogk)。

每处理完相邻两条垂线之间的线段，我们回答横坐标也处于这两条垂线之间的

询问。

这样做的时间复杂度为O(klogk+qlogq)，空间复杂度O(k)。

2

2.4算法4

将上面的离线算法改成算法，只需要将用来线段的平衡树可持久化即

可。

我们使用函数式Treap，使用两个操作Merge和Split分别表示将两个有序序列

前后拼接在一起，以及将一个有序序列分离成前后两个大小给定的有序序列，这

两个操作互