computational-geometry - 某条线上的点数

Question

考虑二维平面上的一些点并使用f(x)=ax函数，其中b=0。假设一个点是1x1正方形。

现在我们要告诉f(x)函数和y线之间有多少个点，如下图所示。

黑点有效，白点无效。我们还说，如果满足以下条件，则该点是有效的:

与y轴相交；

或带有功能f(x)；

或在它们之间。

如图所示:

假设我们不删除任何要点，也不添加它们，那么我们如何解决呢？除了标准蛮力外，还有其他方法吗？

Answer 1

如果我理解这一权利，则这些点是随机的，并由其坐标给您，并且线也给您。如果真是这样，那么就没有关于点之间任何关系的先验知识，因此您必须按照给定的顺序遍历它们，然后将它们的x坐标与0进行比较，并将它们的y坐标与f(x )。如果某个点通过了支票，则您会增加计数器，否则不会。该算法运行时间为O(n)，我高度怀疑如果没有一些有关这些点的额外信息，您可以做得更好。