点在多边形

Question

我试图做一些SPOJ问题是https://www.spoj.pl/problems/FSHEEP/

我们必须找出如果点在多边形内。如我们所见，它不是凸多边形（来自问题的图像）。

我试图用维基百科或任何其他网站上描述的Ray Casting算法在O（n * m）时间内解决它。

但是如何在O（n log m）中解决它？ 换句话说，如何在对数时间检查点是否在多边形？

干杯

Answer 1

由于这是一门功课式的问题，我给你的功课式的帮助。经验法则：无论何时你看到log n，你都应该考虑“binary-something”（搜索，树等）。当你看到n个记录时，你应该考虑“排序”。你会惊奇地发现它的工作频率。你可以在你的big-O限制内对顶点和二进制搜索进行排序吗？

UPDATE：

我不想让你扫兴：你实际上是在给定的分类顺序的多边形顶点，所以重要的是排序为你做。您不需要在角度空间中创建区间，使用排序顶点数组的索引作为区间。

把你的光线从农民身上投射到顶点。如果是顺时针，则顺时针进行二分搜索。如果是逆时针方向，则进行二进制搜索。两个顶点和农民形成一个边界三角形。羊在三角形边界吗？

疯狂懒伪代码：

if vertex[m] and vertex[0] trivially bound the sheep 
    l=m, r=0 
else 
    l=0, r=m 
    while (r-l > 1) 
    middle = (r-l)/2 
    if vertex[l] and vertex[middle] bound sheep 
     r = middle 
     continue 
    else if vertex[middle] and vertex[r] bound sheep 
     l = middle 
     continue 
    else some_jerk_gave_you_a_sheep_on_a_ray 

check vertex[l],vertex[r],farmer triangle 

二进制搜索是为O（log M）。三角形检查是O（1）。迭代n只绵羊会给你O（n）* O（log m）* O（1）= O（n log m）。