可以与单条直线相交的最大可能矩形数 [英] Maximum possible number of rectangles that can be crossed with a single straight line

问题描述

我发现了这个挑战问题，说明如下:

I found this challenge problem which states the following :

假设在 XY 平面上有 n 个矩形.编写一个程序，计算在该平面上绘制的单条直线所能穿过的矩形的最大可能数量.

Suppose that there are n rectangles on the XY plane. Write a program to calculate the maximum possible number of rectangles that can be crossed with a single straight line drawn on this plane.

我已经头脑风暴了很长时间，但找不到任何解决方案.也许在某个阶段，我们使用了动态编程步骤，但不知道如何开始.

I have been brainstorming for quite a time but couldn't find any solution. Maybe at some stage, we use dynamic programming steps but couldn't figure out how to start.

推荐答案

这是一个 O(n^2 log n) 解决方案的草图.

Here is a sketch of an O(n^2 log n) solution.

首先，预赛与其他答案共享.当我们有一条线穿过一些矩形时，我们可以将它平移到两个边中的任何一个，直到它穿过某个矩形的一个角.之后，我们将该角固定为旋转中心，并将线旋转到两侧中的任何一个，直到它穿过另一个角.在整个过程中，我们的直线和矩形边之间的所有交点都在这些边上，所以交叉点的数量保持不变，直线穿过的矩形数量也是如此.因此，我们可以只考虑通过两个矩形角的线，其上限为 O(n^2)，与任意线的无限空间相比，这是一个可喜的改进.

First, the preliminaries shared with other answers. When we have a line passing through some rectangles, we can translate it to any of the two sides until it passes through a corner of some rectangle. After that, we fix that corner as the center of rotation and rotate the line to any of the two sides until it passes through another corner. During the whole process, all points of intersection between our line and rectangle sides stayed on these sides, so the number of intersections stayed the same, as did the number of rectangles crossed by the line. As a result, we can consider only lines which pass through two rectangle corners, which is capped by O(n^2), and is a welcome improvement compared to the infinite space of arbitrary lines.

那么，我们如何有效地检查所有这些行?首先，让我们有一个外循环，它固定一个点 A，然后考虑所有通过 A 的线.A有O(n)个选择.

So, how do we efficiently check all these lines? First, let us have an outer loop which fixes one point A and then considers all lines passing through A. There are O(n) choices of A.

现在，我们已经固定了一个点 A，并且想要考虑所有通过所有其他角 B 的线 AB.为了做到这一点，首先根据 AB 的极角，或者换句话说，轴 Ox 和向量 AB 之间的角度对所有其他角 B 进行排序.角度是从 -PI 到 +PI 或从 0 到 2 PI 或以其他方式测量的，我们切割圆以对角度进行排序的点可以是任意的.排序在 O(n log n) 内完成.

Now, we have one point A fixed, and want to consider all lines AB passing through all other corners B. In order to do that, first sort all other corners B according to the polar angle of AB, or, in other words, angle between axis Ox and vector AB. Angles are measured from -PI to +PI or from 0 to 2 PI or otherwise, the point in which we cut the circle to sort angles can be arbitrary. The sorting is done in O(n log n).

现在，我们有点 B₁, B₂, ..., B_k 按 A 点周围的极角排序 (它们的数字 k 类似于 4n-4，所有矩形的所有角，除了点 A 是角的那个).首先，查看线 AB₁ 并计算该线在 O(n) 中穿过的矩形数量.之后，考虑将 AB₁ 旋转到 AB₂，然后 AB₂ 到 AB₃，一直到AB_k.轮换期间发生的事件如下:

Now, we have points B₁, B₂, ..., B_k sorted by the polar angle around point A (their number k is something like 4n-4, all corners of all rectangles except the one where point A is a corner). First, look at the line AB₁ and count the number of rectangles crossed by that line in O(n). After that, consider rotating AB₁ to AB₂, then AB₂ to AB₃, all the way to AB_k. The events which happen during the rotation are as follows:

• 当我们旋转到 AB_i，并且 B_i 是我们顺序中某个矩形的第一个角时，交叉的矩形数量增加 1旋转线一碰到 B_i.

• When we rotate to AB_i, and B_i is the first corner of some rectangle in our order, the number of rectangles crossed increases by 1 as soon as the rotating line hits B_i.

当我们旋转到 AB_j，并且 B_j 是我们顺序中某个矩形的最后一个角时，交叉的矩形数量减少 1线一转过 B_j.

When we rotate to AB_j, and B_j is the last corner of some rectangle in our order, the number of rectangles crossed decreases by 1 as soon as the line rotates past B_j.

在排序之后，但在考虑有序事件之前，可以通过一些 O(n) 预处理来确定哪些角是第一个和最后一个.

Which corners are first and last can be established with some O(n) preprocessing, after the sort, but before considering the ordered events.

简而言之，我们可以旋转到下一个此类事件并更新在 O(1) 中交叉的矩形数量.总共有 k = O(n) 个事件.剩下要做的是在整个算法中跟踪这个数量的全局最大值.答案就是这个最大值.

In short, we can rotate to the next such event and update the number of rectangles crossed in O(1). And there are k = O(n) events in total. What's left to do is to track the global maximum of this quantity throughout the whole algorithm. The answer is just this maximum.

整个算法的运行时间为 O(n * (n log n + n + n))，也就是 O(n^2 log n)，正如宣传的那样.

The whole algorithm runs in O(n * (n log n + n + n)), which is O(n^2 log n), just as advertised.

这篇关于可以与单条直线相交的最大可能矩形数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！