一道挺好玩的算法题，不知道各位有没有更好的想法

[XiongZaizi]

小弟这几天在做算法题目，看到一个很 interesting 的题目，贴图如下：

简单描述下题目内容：这根木棍向右倒，在经过点 a 坐标之后，下一次在重合到一点时，输出离原点最近的那一点的坐标。 举个栗子：如下图

上图重合点是 5,3 这个点，接下来重合的点是 2,1 4,2 6,3 那么离原点最近的点就是 2,1。

我的想法就是： 1、穷举出木棍 l 能扫过的所有的点，然后计算每个点到原点的距离，以及和横轴的夹角。按照角度进行快速排序；

2、计算与点 a 重合时，木棍和横轴的夹角，抽取出小于该夹角的所有点

3、对抽取出来的点按照距离进行一次遍历，找到距离原点最小的点进行输出

总感觉这个算法有点复杂，不知道有没有更巧妙地算法？还请大家开动脑洞讨论讨论

[GtDzx]

感觉就是个排序题。按极角和距离排序不就完了...

[hxsf]

有意思的题目。
回家电脑码字

[imn1]

A(x0, y0)
棍长 s0
所经过的点 Pn(xn, yn)

Pn 满足
Xn<=S0 && Yn/Xn 反正切的角度<Y0/X0 反正切角度

Pn 到原点距离 Sn
Sn^2 = Xn^2 + Yn^2 = (Xn + Yn)^2 - 2*Xn*Yn
所以，Xn + Yn 最小值为所求
当有两点或以上满足此条件时，Xn 与 Yn 数值最接近的为所求

[blankme]

y = 1
x = min(n), where arctan(1 / n) < arctan(y0 / x0)

[hxsf]

到家，开更。

最暴力的方法，算一下每个点的角坐标(θn, ln)，排除掉 ln > l 棍 和 角度小于 点 a 的，然后根据θn 排序。取第一个。

==========================当然不是这么简单啦==============================

我们真的需要算这么多点么？

其实我们要算的，只有 线段 OA 附近的点啊。（ O 指原点，A 点坐标设为（ a，b ））

OA 附近的点（记为集合 D ）如何得出？

D 中的[ (x1, y1)，(x2, y2)，……(xn, yn)] 满足

1. x 属于 0~Xmax 上的所有整数
由数学方案可知，Xmax = a * 根号（ L 棍^2 - a^2 - b^2 ）， 及 n = int （ Xmax ）
2. 因为要找 yn/xn 尽可能大的，所以 yn < xn * b/a 的基础上, yn > yn-1 + 1

于是要计算的点就变成这样：



完结！

[hxsf]

@hxsf #25

更正

>>>>>>>>>>
2. 因为要找 yn/xn 尽可能大的，所以 yn < xn * b/a 的基础上, yn > yn-1 + 1
==========
2. 因为要找 yn/xn 尽可能大的，所以 yn < xn * b/a 的基础上, yn > yn-1
<<<<<<<<<<

忘记说了。红色点是要算的点，蓝色点是 满足 yn < xn * b/a 但不满足 yn > yn-1

[XiongZaizi]

@imn1 那这样还是要穷举计算出所有的点，感觉如果 l 很大的话计算量会很多

[XiongZaizi]

@hxsf 学习了。但是我有点没有明白 xmax 的计算公式是怎样得到的？

[hxsf]

@XiongZaizi #28

你一说发现算错了。。。尴尬

下面是正确算法

棍子与 A(a, b)重合时的 端点 B 设为 (na, nb)

(na)^2 + (nb)^2 = l^2

就可以算出来了 n^2 = l^2 / (a^2 + b^2)

na = a * 根号( l^2 / (a^2 + b^2) )

[XiongZaizi]

@hxsf 哦哦哦，明白了，是按照比例算的。按照你的方法，可以减少很多计算量，多谢！！！

[XiongZaizi]

@ZyZyZzz 好的。

[imn1]

@XiongZaizi
怎么需要穷举所有点呢？

所有的点都是已知坐标的吧？
从最小值开始计算角度是否符合就够了
如果是要尽可能大，就从 Xn<=S0 最大值开始，只要(Xn_1<Xn && Yn_1<Yn)符合就可以结束了

[bumz]

@XiongZaizi #31 这是什么书呀

[XiongZaizi]

@imn1 啊，有理。一时没转过弯来

[XiongZaizi]

@bumz 基友正在看的书，我也不知道叫啥。今天偶然开始讨论起来的题目。