Algorytm znaleźć linie Bracketing jeden punkt

Question

Mam następujące zadania:

w programie należy rysować linie na ekranie mapy bitowe. Tablica par n reali (ai,bi) zdefiniowała linie nyi = ai*x + bi. Linie zostały zamówione w x -interval [0, 1] w tym sensie, że yi < yi+1 dla wszystkich wartości i między 0 i n-2 i dla wszystkich wartości x w [0, 1]

Mniej formalnie, linie nie dotykać w pionie płyta. Biorąc pod uwagę punkt (x,y), gdzie 0 < x < 1, chcemy określić dwie linie, które otaczają punkt.

Jak możemy szybko rozwiązać ten problem?

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); 
} 

Istnieje jednak niewielki haczyk. Patrz poniższy obrazek:

Czy można powiedzieć, że punkt F jest "ujęty" przez dwie linie w [0,1] x [0,1] ?? Jaka jest poprawna odpowiedź w tym przypadku?