寻找最大点数的算法
Algorithm for finding the maximum number of points
令 P = {P1(x1, y1), P2(x2, y2), . . . , Pn(xn, yn)} 是位于矩形内的一组 n 个点，使得 none 个点接触其边界。矩形的左上角位于原点 O(0, 0)。平面镜沿矩形的下边缘放置（如图所示）。在O处放置一个点光源，该光源可以任意角度θ发出单束光。
编写一个算法（伪代码）来计算 θ 的值，其中相应的光线及其反射一起通过集合 P 的最大点数。
例如图中，角度为θ1的光线R1（用实线表示），通过3个点，而角度为θ2的光线R2（用虚线表示），只通过2个点。只有当您的算法花费 O(n log n) 时间时，您才能获得满分。
................................................ ...
如果是求 θ 的值使得平面上的最大点数落在入射光线上，我会做这道题。
那时我会通过将光线聚焦在每个点上来计算每个点的 θ 值，并将这些点的 θ 值存储在一个数组中。
那么我们的问题将简化为查找数组中重复元素的最大数量。这可以在 O(n) 时间内解决。
但我不知道如何处理反射光线。我在互联网上搜索但徒劳无功。请帮忙。
镜子的位置未指定，因此为了具体起见，我们假设 y = -1。要将光线反射到点 (x, y) 和 y > -1，我们需要从 (0, 0) 瞄准 (x/(y+1), -1)。这个点可以通过观察原点和反射点构成的直角三角形与目标和反射点构成的直角三角形相似
一种方法是使用 method of images，它通过在反射面的另一侧引入 'mirror points' 来取代反射效果。
假设镜子是由平面y=-b定义的，那么每个点(x_i, y_i)将被用来生成自身的反射版本。该额外点将具有相同的 x 坐标，但在与镜子对称相反的距离上具有 y 坐标，即 -b - (y_i + b) 即 -2b - y_i。 （在你的例子中，所有 y_i 都是负数。）每个点的反射版本精确地模拟了从镜子反弹后到达原始点的光线的几何形状。此后，我们可以忽略镜像，只处理2N个点。
因此，您算法的伪代码可能 运行 如下所示：
- 使用以下方法在镜面下方生成一组额外的 N 个点
图片的方法
- 分别计算2N个点与原点的夹角，
使用
atan2(y_i, x_i)。这需要N阶的时间。
- 按点与原点的角度对点进行分组，这等价
对它们进行排序并检测列表中相邻值之间的变化，
这需要 N(log N) 阶时间。
- 计算每组的点数。 （这花费的时间少于 N。）
- 找到成员数量最多的组。
令 P = {P1(x1, y1), P2(x2, y2), . . . , Pn(xn, yn)} 是位于矩形内的一组 n 个点，使得 none 个点接触其边界。矩形的左上角位于原点 O(0, 0)。平面镜沿矩形的下边缘放置（如图所示）。在O处放置一个点光源，该光源可以任意角度θ发出单束光。
编写一个算法（伪代码）来计算 θ 的值，其中相应的光线及其反射一起通过集合 P 的最大点数。
例如图中，角度为θ1的光线R1（用实线表示），通过3个点，而角度为θ2的光线R2（用虚线表示），只通过2个点。只有当您的算法花费 O(n log n) 时间时，您才能获得满分。
................................................ ...
如果是求 θ 的值使得平面上的最大点数落在入射光线上，我会做这道题。
那时我会通过将光线聚焦在每个点上来计算每个点的 θ 值，并将这些点的 θ 值存储在一个数组中。
那么我们的问题将简化为查找数组中重复元素的最大数量。这可以在 O(n) 时间内解决。
但我不知道如何处理反射光线。我在互联网上搜索但徒劳无功。请帮忙。
镜子的位置未指定，因此为了具体起见，我们假设 y = -1。要将光线反射到点 (x, y) 和 y > -1，我们需要从 (0, 0) 瞄准 (x/(y+1), -1)。这个点可以通过观察原点和反射点构成的直角三角形与目标和反射点构成的直角三角形相似
一种方法是使用 method of images，它通过在反射面的另一侧引入 'mirror points' 来取代反射效果。
假设镜子是由平面y=-b定义的，那么每个点(x_i, y_i)将被用来生成自身的反射版本。该额外点将具有相同的 x 坐标，但在与镜子对称相反的距离上具有 y 坐标，即 -b - (y_i + b) 即 -2b - y_i。 （在你的例子中，所有 y_i 都是负数。）每个点的反射版本精确地模拟了从镜子反弹后到达原始点的光线的几何形状。此后，我们可以忽略镜像，只处理2N个点。
因此，您算法的伪代码可能 运行 如下所示：
- 使用以下方法在镜面下方生成一组额外的 N 个点 图片的方法
- 分别计算2N个点与原点的夹角，
使用
atan2(y_i, x_i)。这需要N阶的时间。 - 按点与原点的角度对点进行分组，这等价 对它们进行排序并检测列表中相邻值之间的变化， 这需要 N(log N) 阶时间。
- 计算每组的点数。 （这花费的时间少于 N。）
- 找到成员数量最多的组。