如何定义一条直线，使其穿过尽可能多的矩形？

Question

3

我正在寻找一种解决这个问题的算法，除了强化学习和那些运行时间长的算法。在x-y平面上，有n个矩形。一条直线最多可以穿过多少个矩形？

输入

矩形数量为n。
第i个矩形的左上坐标由x[i]，y[i]给出。
它的宽度和高度由w[i]，h[i]给出。

n
x[0] y[0] w[0] h[0]
x[1] y[1] w[1] h[1]
・
・
x[n-1] y[n-1] w[n-1] h[n-1]

案例1：

Input
4
0    0    1    1
9999 0    1    1
0    9999 1    1
9999 9999 1    1

Output
2

案例2：

Input
6
2    1    4    3
1   10    1    3
5    7    5    4
8    8    3    2
13   4    3    1
17   1    1   14

Output
5

- Kosuke Takahashi

你可以作弊，不必假设它需要是一条“直”的线。 - Mr Lister

交叉线必须起始于0/0吗？ - sven.kwiotek

交叉的直线不一定要有0/0。 - Kosuke Takahashi

你目前尝试了什么，哪一部分让你感到困难？ - Jamey

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Syed Waris · Answer 1

我将与您分享一种方法。您可以计算每个矩形的中心点，这样你就能得到与矩形数量相同的中心点。例如，对于100个矩形，您将在xy平面上获得100个中心点。

现在，通过这些100个点，您可以构建一个最佳拟合直线。您可以在这里和这里了解有关最佳拟合直线的知识。

所得到的直线将经过大部分矩形。