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

-3

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

在下图中，红点是基点，黑点是基准点。黄色区域是黑点最多的地方。如果其中一个黑点在其中一条线上，则认为该点位于线条之间。

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

我发现，在时间复杂度为O解决方案（N * N），但是这是太慢了。

2012-04-26 user1359532

您的意思是“连接这两条线的线上的最大点数”？如果是这样，它是否必须垂直于它们？如果垂直，那么它将与线条之间的距离相同。否则，您可以计算角点之间的距离，并选择最长的。如果你不是在谈论某一方面的问题，那么我们可能需要更多的解释。 – 2012-04-26 19:20:14

是否需要遵循C++的问题？ – 2012-04-26 19:25:59

致下流者：这是一个合理的问题。也许是错误的，并没有表现出自己的努力的迹象，但既不是外在的也不是“不是真正的问题”。 – 2012-04-26 19:45:19

想象一下，你的两条线穿过两个基点。线条之间的条的宽度为0，并且里面没有点（或者有一些点，这取决于“内部”的定义）。

现在想象两条线缓慢地逆时针旋转，同时保持平行。完成半圈后，他们与之前的位置相同。随着线条旋转，它们穿过你的点，从而进入和离开线条之间的条。

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

来源

2012-04-26 19:42:51

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

回答

相关问题