O(nlogn) 分而治之算法找到可见线
O(nlogn) divide and conquer algorithm to find visible lines
我正在尝试解决附图中显示的问题。我得到了划分部分，您可以在其中递归地将线集分成两半，并且可以看到具有最小和最大斜率的线。
虽然我不知道如何进行合并部分，但我也不理解。
凭直觉，起初，我认为如果没有三条线在一点相交，最终所有线都会可见。
还有，conquer 部分就是我会去掉不可见的线...据我了解，在conquer 阶段之前不应该去掉任何线。
如果有人能为我们这些脑子有点慢的人解释一下，我将不胜感激！ :)
考虑一个 3 行示例。你有两个选择。 a) 只有 2 行可见 b) 所有 3 行都可见。
所以你需要判断中间那个是否可见。为此，您可以计算外部 2 条线（称为 A）的交点。如果A在中线以上则中间的隐藏，如果在下方则可见（画两个图就很明显了）。
要确定该点是在上方还是下方，请将其坐标代入线方程 (y = ax + b)。如果 y > ax + b 则该点在线上方，如果 y < ax + b 则该点在线下方，如果 y = ax + b 则该点在线上（根据问题不应该发生）。
为了解决你的问题，我会按照斜率的顺序排列线，然后尝试将它们添加到解决方案中。每次添加新行时检查前一行是否仍然可见，如果不可见则将其删除（根据需要重复多次，因为新行可能隐藏的不仅仅是前一行）。
如果您坚持要进行合并，则需要在合并行上应用此逻辑来计算从中间删除了多少行。
我正在尝试解决附图中显示的问题。我得到了划分部分，您可以在其中递归地将线集分成两半，并且可以看到具有最小和最大斜率的线。
虽然我不知道如何进行合并部分，但我也不理解。
凭直觉，起初，我认为如果没有三条线在一点相交，最终所有线都会可见。
还有，conquer 部分就是我会去掉不可见的线...据我了解，在conquer 阶段之前不应该去掉任何线。
如果有人能为我们这些脑子有点慢的人解释一下，我将不胜感激！ :)
考虑一个 3 行示例。你有两个选择。 a) 只有 2 行可见 b) 所有 3 行都可见。
所以你需要判断中间那个是否可见。为此，您可以计算外部 2 条线（称为 A）的交点。如果A在中线以上则中间的隐藏，如果在下方则可见（画两个图就很明显了）。
要确定该点是在上方还是下方，请将其坐标代入线方程 (y = ax + b)。如果 y > ax + b 则该点在线上方，如果 y < ax + b 则该点在线下方，如果 y = ax + b 则该点在线上（根据问题不应该发生）。
为了解决你的问题，我会按照斜率的顺序排列线，然后尝试将它们添加到解决方案中。每次添加新行时检查前一行是否仍然可见，如果不可见则将其删除（根据需要重复多次，因为新行可能隐藏的不仅仅是前一行）。
如果您坚持要进行合并，则需要在合并行上应用此逻辑来计算从中间删除了多少行。