Изменения

Пусть дана прямая с точками на ней и отрезок. Необходимо указать, какие из точек лежат на этом отрезке.

Задача тривиальна — нужно оставить только те точки, которые находятся между началом и концом отрезка.

На практике для быстрого осуществления запроса нужно хранить точки в отсортированном массиве и пользоваться двоичным поиском. В C++ данная задача решается с помощью функций из STL - upper_bound и lower_bound.

Алгоритм работает за <tex>O(\log n)</tex>.

== Двумерный случай ==