c++ - 有多少条线段将在一个平面上与一条水平线相交？找到这个的最有效方法是什么

Question

我正在尝试解决这个 Cyber​​chef 挑战：

在平面上给你 N 个点（编号为 1 到 N）；对于每个有效的 i，第 i 个点是 Pi=(i,Ai)。它们之间有 N-1 个线段（编号为 1 到 N-1）；对于每个有效的 i，第 i 个线段是通过连接点 Pi 和 Pi+1 形成的。

给你 Q 个水平线段。每个查询水平线段由两个点表示，从点 (x1,y) 到点 (x2,y)（它停止并且不再传播）。对于每个水平线段，您必须从它在途中碰撞的那些（N-1 条线段）中找到线段的数量。

所以这就是问题所在：

• 2<=N<= 100000
• 1<=Q<= 100000

谁能教我在时间复杂度方面哪种方法最好和最有效？

Answer 1

因此，您拥有唯一的折线，并希望检查许多查询是否与水平线段相交。

在该折线上构建某种二进制空间分区(BSP)是值得的。在这种情况下，您可以及时检查交叉口O(log(n))，因此总时间为O(nlogn)+O(qlogn)（构建和检查）

---

如果你的折线幸运的是凸多边形（没有一个闭合边），那么事情就非常简单了——只需按 Y 坐标对边进行排序，然后只检查那些相交的查询 Y（二分搜索，每个查询的 log(n)）。在一般情况下（非凸），您的折线可能看起来像WMWMWMW，您必须检查太多边。

Answer 2

我用kd树来解决这个问题。也不要问那些持续挑战的问题。

Answer 3

所以扫线算法是你基本上需要知道的，为了解决这个问题。