Максимальное количество точек между двумя параллельными линиями

Question

Я получаю N + 2 точки с целыми координатами. 2 из них являются базовыми. Через эти базовые точки нужно провести две параллельные линии. Каково максимальное количество точек, расположенных между двумя параллельными линиями? Извините за мой английский и спасибо заранее!

На следующем рисунке КРАСНЫЕ точки являются базовыми, ЧЕРНЫЕ - это обычные точки. Желтая область - это максимальное количество черных точек. Если одна из черных точек включена в одну из строк, считается, что эта точка IS находится между линиями.

http://i.stack.imgur.com/Awhg6.png

Я нашел решение в время сложности O (N * N), но это слишком медленно.

Answer 1

Представьте, что ваши две линии проходят через обе базовые точки. Ширина полосы между линиями равна 0, и внутри нее нет точек (или есть некоторые точки, в зависимости от вашего определения «внутри»).

Теперь представьте, что две линии медленно вращаются против часовой стрелки, оставаясь параллельными. После окончания половины хода они находятся в том же положении, что и раньше. Когда линии вращаются, они проходят через ваши точки, которые тем самым входят и оставляют полосу между линиями.

Предполагая, что линии фиксируют число оборотов за единицу времени, вычислите для каждой точки время ее ввода полосы между линиями и время ее выхода из полосы. (Эти времена в основном являются углами). Сортируйте оба вида событий вместе. Теперь просмотрите события, подсчитав +1 для каждого события записи и -1 для каждого события выхода. Для событий, которые происходят в одно и то же точное время, сначала выполните сначала -1 или +1, в зависимости от вашего определения «внутри». Следите за максимальным количеством отсчетов.