Алгоритм нахождения линий, заключающих в скобки одну точку

Question

У меня есть следующая задача:

В программе мы должны рисовать линии на немного отображенном дисплее. Массив n пар вещественных чисел (a<sub>i</sub>,b<sub>i</sub>) определил n строк y<sub>i</sub> = a<sub>i</sub>*x + b<sub>i</sub>. Строки были упорядочены с интервалом x [0, 1] в том смысле, что y<sub>i</sub> < y<sub>i+1</sub> для всех значений i между 0 и n-2 и для всех значений x в [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] ?? Какой правильный ответ в этом случае?