找到包围一个点的线的算法

Question

我有以下任务:

In the program we should draw lines on a bit mapped display. An array of n pairs of reals (a<sub>i</sub>,b<sub>i</sub>) defined the n lines y<sub>i</sub> = a<sub>i</sub>*x + b<sub>i</sub>. The lines were ordered in the x-interval [0, 1] in the sense that y<sub>i</sub> < y<sub>i+1</sub> for all values of i between 0 and n-2 and for all values of x in [0, 1]

不太正式的是，垂直板中的线条不接触。给分(x,y) , 其中0 < x < 1 , 我们想确定两条线将点括起来。

我们怎样才能快速解决这个问题？

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] 中的两条线“括起来”了吗？在这种情况下，正确答案是什么？