algorithm - 两条平行线之间的最大点数

Question

给我 N+2 个整数坐标点。其中2个是基点。需要通过给定的基点绘制两条平行线。位于两条平行线之间的最大点数是多少？对不起我的英语，提前谢谢！

在下图中，红色的点是基点，黑色的点是正常点。黄色区域是最大数量的黑点。如果其中一个黑点位于其中一条线上，则认为该点位于线之间。

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

我找到了时间复杂度 O(N*N) 的解决方案，但这太慢了。

Answer 1

想象你的两条线穿过两个基点。线之间的条带宽度为 0，内部没有点（或有一些点，取决于您对“内部”的定义）。

现在想象两条线逆时针缓慢旋转，同时保持平行。转了半圈后，他们的位置和之前一样。当线条旋转时，它们会穿过您的点，从而进入和离开线条之间的条带。

假设线条每单位时间进行固定的旋转次数，计算每个点它进入线条之间的条带的时间，以及它离开条带的时间。（这些时间基本上是角度）。将这两种事件排序在一起。现在检查事件，每个进入事件计数 +1，每个退出事件计数 -1。对于同时发生的事件，首先执行 -1 或首先执行 +1，这再次取决于您对“内部”的定义。跟踪最大计数。