我得到了一个严格的S边凸多边形和Q查询来处理。
多边形的所有点和查询点都以 (x,y) 对形式给出。多边形的点按逆时针顺序给出。
上述变量受限于1<=S<=10^6和1<=Q<=10^5和1<=|x|,|y|<=10^9。
对于每个查询，如果给定点位于多边形内，我应该输出 Yes；否则，不。
我尝试使用 O(S)包含测试（光线投射），但它对于更大的测试用例超时，但也没有通过所有初步测试。
显然，实现并没有涵盖所有边缘情况，我了解了这个问题的特定算法，它可以使用二进制搜索回答O(log S)中的每个查询，但我不知道如何从伪代码（第一次做计算几何）。
任何人都可以为我提供涵盖所需时间复杂度（Q log S）内所有边缘情况的算法，或者指导我找到实现它的页面或论文吗？
首先，您可以将凸多边形分成左右两部分，从上点开始，到下点结束。两部分中的点已经按-坐标排序y。
假设查询点有坐标(qx, qy)。现在，您可以尝试（使用二分搜索）从左侧部分和从右侧部分中找到与 line 相交的段y = qy。如果您可以找到两个线段并且qx位于x线段与线相交的坐标之间y = qy，则它在多边形内。
查询的复杂度是O(log(S))。
你可以做一个扫描线算法。您需要按 x 坐标对 Q 点进行排序。然后找到具有最低 x 的 S 点，并考虑一条沿 x 轴移动的线。您需要跟踪多边形的两侧。
然后沿着多边形和 Q 集合在升序的 x 坐标中移动。对于每个点，您现在只需检查它是否在您正在跟踪的两条线之间。
如果 Q 没有排序，复杂度是 O(Q logQ + S)，如果 Q 已经排序，复杂度是 O(Q+S)。
无需排序，凸多边形已经排序！
对于凸多边形，点定位既快速又简单：使用顶点 0 和顶点 S/2 之间的直线将多边形一分为二。签名区域测试会告诉您测试点位于哪一侧以及保留哪一半（一半也是凸多边形）。
继续递归直到 S=3 并与第三边的支撑线进行比较。
每个查询总共进行 O(Log(S)) 次测试。
（数字显示拆分的顺序。）