这是一个创建于 2759 天前的主题，其中的信息可能已经有所发展或是发生改变。
小弟这几天在做算法题目，看到一个很 interesting 的题目，贴图如下：
简单描述下题目内容：这根木棍向右倒，在经过点 a 坐标之后，下一次在重合到一点时，输出离原点最近的那一点的坐标。 举个栗子：如下图
上图重合点是 5,3 这个点，接下来重合的点是 2,1 4,2 6,3 那么离原点最近的点就是 2,1。
我的想法就是： 1、穷举出木棍 l 能扫过的所有的点，然后计算每个点到原点的距离，以及和横轴的夹角。按照角度进行快速排序；
2、计算与点 a 重合时，木棍和横轴的夹角，抽取出小于该夹角的所有点
3、对抽取出来的点按照距离进行一次遍历，找到距离原点最小的点进行输出
总感觉这个算法有点复杂，不知道有没有更巧妙地算法？还请大家开动脑洞讨论讨论
 |
1
grimpil 2017-05-16 10:40:27 +08:00 via Android
题目看不明白。点 a 是哪个点？重合到一点是什么意思？
|
 |
2
blankme 2017-05-16 10:48:21 +08:00 via Android
建议贴原题，不要“简单描述题目内容”，你根本没描述清楚题目。
|
 |
3
yangff 2017-05-16 10:54:13 +08:00
没理解错的话，没跨过(1,1)之前最近的是(1,1)，跨过(x,1)之后最近的是(x+1,1)；因为只需要考虑 gcd(x,y)==1 的点，所以扫过符合要求的 x 的时候，每个 x 显然能符合要求的最小的 y 是 1
|
 |
4
XiongZaizi OP @blankme 原题是日语的，我只能简单的进行翻译了。。。哪里不明白可以说一下
|
 |
5
jmc891205 2017-05-16 11:04:37 +08:00
那些斜率一样的点只要记一个到原点距离最小的就可以了
这样你的第一步快排之后就有了一个按斜率（角度）递增的数组 之后只要拿 A 点的斜率做一次二分查找 找到的那个点的前一个点就是结果 |
|
6
XiongZaizi OP @grimpil a 是随机输入的一个点，是棍子能够扫到的任何一点；重合到一点就是就是棍子在向下扫的时候，接触到的点。可以看第二个图，图中画的那条线就假设是棍子，在向下倒的时候，接触到了 5,3 这个点，这种情况就叫做重合
|
 |
7
Vinty 2017-05-16 11:05:59 +08:00
大概就是求一个比 a/b 小的最大的两个整数之比 x/y，x/y 有公约数，化简一下即可
|
 |
8
whalegia 2017-05-16 11:08:27 +08:00
重合是什么意思？
为什么 （ 5，3 ）后是（ 2，1 ），（ 2，1 ）后是（ 4，2 ）？ 感觉我哪里都不明白，对不去语文老师 |
|
9
XiongZaizi OP @jmc891205 有道理呢，这样能减少很大一部分的操作量了。多谢了
|
|
10
XiongZaizi OP @whalegia 第二张图中实线是假设的棍子，这根棍子没有题目中的那么长，此时棍子接触到了点 5,3，棍子继续向下倒的时候，最先接触点 2,1，再接触点 4,2。
|
|
11
Vinty 2017-05-16 11:14:57 +08:00
接 7l，这个值应该等于(ma-1)/(mb-1),m 是令该点在可行域内的最大整数
|
|
12
XiongZaizi OP @yangff 那这样看来只有 y=1 的点是符合要求的，说的有道理
|
|
13
XiongZaizi OP @Vinty “大概就是求一个比 a/b 小的最大的两个整数之比 x/y，x/y 有公约数，化简一下即可”，这一步是求出下一个杰出的点的吧？还有后面那个公式是咋计算的？
|
 |
14
liuminghao233 2017-05-16 14:00:41 +08:00 via iPhone
根本就不知道你在说什么 什么 a 点
|
|
15
Vinty 2017-05-16 14:37:41 +08:00
@XiongZaizi 11l 的公式是我猜的，好像不对。。一是只考虑了小于 45°的情况，二是对可行域处理的不好。如果点的数量比较少的话，就列出可行域内的所有点按正切值做个排序就行了。如果是点非常复杂的话，那就找到目前过（ a,b ）这条线和边界的交点（ u,v ），向下取整得到（ u'，v'）。比较（ u'，v'），（ u'+1，v'），（ u'，v'-1 ），（ u'+1，v'-1 ）四点即可，也许还有（ u'-1，v'-1 ）。
反正就是比较周围几个点看在不在可行域内哪个最大，具体哪几个也许可以简化一下。 |
 |
16
imn1 2017-05-16 15:16:55 +08:00
下一次在重合到一点时，输出离原点最近的那一点的坐标
------------------------------------------------------------------------- 这句话是要再解释清楚的 “下一次在重合到一点时”，换言之，重合 A 到这次重合中间没有再重合任何点了，下半句“那一点”指的是什么？ |
 |
17
lingo 2017-05-16 18:04:39 +08:00
哈哈哈哈哈题目看不懂
|
|
18
XiongZaizi OP @Vinty 恩恩，谢谢了，这样也是一种方法
|
|
19
XiongZaizi OP @imn1 就是棍子在向下倒的这个过程中，会接触到点格中的点，那么假设其中有一时刻棍子和给定的能够接触到的点 a 接触了记为时刻 t1，从这一时刻起开始，棍子继续向下倒，又会接触一个新的点 b，时刻记为 t2。这 t1 和 t2 两个时刻之间，棍子没有和任何的点接触。所要求的就是从 t1 时刻开始，到棍子最终倒在横轴上这一段时间里，棍子所能接触到的所有点中，距离原点最小的一点。
|
 |
20
ZyZyZzz 2017-05-16 18:24:47 +08:00
你直接把日语题干贴出来吧，这里有的是人懂日语
不懂的还可以去机翻 |
 |
21
GtDzx 2017-05-16 18:36:57 +08:00
感觉就是个排序题。按极角和距离排序不就完了...
|
 |
22
hxsf 2017-05-16 18:38:15 +08:00 via iPhone
有意思的题目。
回家电脑码字 |
|
23
imn1 2017-05-16 18:55:57 +08:00
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 数值最接近的为所求 |
|
24
blankme 2017-05-16 19:36:28 +08:00 via Android
y = 1
x = min(n), where arctan(1 / n) < arctan(y0 / x0) |
|
25
hxsf 2017-05-16 19:43:07 +08:00
到家，开更。
最暴力的方法，算一下每个点的角坐标(θ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 于是要计算的点就变成这样：  完结！ |
|
26
hxsf 2017-05-16 19:45:08 +08:00
@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 |
|
27
XiongZaizi OP @imn1 那这样还是要穷举计算出所有的点，感觉如果 l 很大的话计算量会很多
|
|
28
XiongZaizi OP @hxsf 学习了。但是我有点没有明白 xmax 的计算公式是怎样得到的？
|
|
29
hxsf 2017-05-16 21:25:04 +08:00  1
@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) ) |
|
30
XiongZaizi OP @hxsf 哦哦哦，明白了，是按照比例算的。按照你的方法，可以减少很多计算量，多谢！！！
|
|
31
XiongZaizi OP |
|
32
imn1 2017-05-16 21:57:49 +08:00
@XiongZaizi
怎么需要穷举所有点呢？ 所有的点都是已知坐标的吧？ 从最小值开始计算角度是否符合就够了 如果是要尽可能大，就从 Xn<=S0 最大值开始，只要(Xn_1<Xn && Yn_1<Yn)符合就可以结束了 |
 |
33
bumz 2017-05-16 22:00:07 +08:00
@XiongZaizi #31 这是什么书呀
|
|
34
XiongZaizi OP @imn1 啊，有理。一时没转过弯来
|
|
35
XiongZaizi OP @bumz 基友正在看的书，我也不知道叫啥。今天偶然开始讨论起来的题目。
|
Select Language