寻找夹在某一点两侧的线段的算法

Question

我有以下任务：

在位图显示上绘制线条。一组n对实数(a_i,b_i)定义了n条直线y_i=a_i*x+b_i。这些直线按照x区间[0,1]的顺序排列，即对于所有i(0 <= i <= n-2)和x(0 <= x <= 1)，都有y_i < y_i+1。

简单来说，在垂直平面上这些直线不相交。给定一个点(x,y)，其中0 < x < 1，我们希望确定两条夹住该点的直线。

我们如何快速解决这个问题？

- user466534

Answer 1

Function bracket( Real x, Real y, Array a[1..n],b[1..n] of Reals): Returns void 
{
  Integer i = 1;

  While (i<=n && (a[i] * x + b[i]) <= y, i++)

  If (i==1 || i == n+1) 
                       { Print("Not bracket exists");
                         Exit()
                       }
  If (a[i] * x + b[i]) == y)
                       { Print("Point lies on line",i);
                         Exit()
                       }
  Print("Point between lines ", i-1, " and ", i);
}  

然而，有一个小问题。请看下面的图片：

你会说点F被[0,1]x[0,1]中的两条线“括起来”吗？在这种情况下，正确答案是什么？

- Dr. belisarius

---

也许使用二分查找会更快？ - Dialecticus

@Dialecticus 或许我误解了“我们如何快速解决这个问题？”中的OP。如果“快速”意味着O(logn)，那么你是正确的，如果“快速”意味着只需一条指令，上面的“while”循环就可以做到。从未见过“快速”在这个上下文中使用 :) - Dr. belisarius