V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
This topic created in 3269 days ago, the information mentioned may be changed or developed.
小弟这几天在做算法题目，看到一个很 interesting 的题目，贴图如下：
简单描述下题目内容：这根木棍向右倒，在经过点 a 坐标之后，下一次在重合到一点时，输出离原点最近的那一点的坐标。 举个栗子：如下图
上图重合点是 5,3 这个点，接下来重合的点是 2,1 4,2 6,3 那么离原点最近的点就是 2,1。
我的想法就是： 1、穷举出木棍 l 能扫过的所有的点，然后计算每个点到原点的距离，以及和横轴的夹角。按照角度进行快速排序；
2、计算与点 a 重合时，木棍和横轴的夹角，抽取出小于该夹角的所有点
3、对抽取出来的点按照距离进行一次遍历，找到距离原点最小的点进行输出
总感觉这个算法有点复杂，不知道有没有更巧妙地算法？还请大家开动脑洞讨论讨论
 |
1
grimpil May 16, 2017 via Android
题目看不明白。点 a 是哪个点？重合到一点是什么意思？
|
 |
2
blankme May 16, 2017 via Android
建议贴原题，不要“简单描述题目内容”，你根本没描述清楚题目。
|
 |
3
yangff May 16, 2017
没理解错的话，没跨过(1,1)之前最近的是(1,1)，跨过(x,1)之后最近的是(x+1,1)；因为只需要考虑 gcd(x,y)==1 的点，所以扫过符合要求的 x 的时候，每个 x 显然能符合要求的最小的 y 是 1
|
 |
4
XiongZaizi OP @blankme 原题是日语的，我只能简单的进行翻译了。。。哪里不明白可以说一下
|
 |
5
jmc891205 May 16, 2017
那些斜率一样的点只要记一个到原点距离最小的就可以了
这样你的第一步快排之后就有了一个按斜率（角度）递增的数组 之后只要拿 A 点的斜率做一次二分查找 找到的那个点的前一个点就是结果 |
|
6
XiongZaizi OP @grimpil a 是随机输入的一个点，是棍子能够扫到的任何一点；重合到一点就是就是棍子在向下扫的时候，接触到的点。可以看第二个图，图中画的那条线就假设是棍子，在向下倒的时候，接触到了 5,3 这个点，这种情况就叫做重合
|
 |
7
Vinty May 16, 2017
大概就是求一个比 a/b 小的最大的两个整数之比 x/y，x/y 有公约数，化简一下即可
|
 |
8
whalegia May 16, 2017
重合是什么意思？
为什么 （ 5，3 ）后是（ 2，1 ），（ 2，1 ）后是（ 4，2 ）？ 感觉我哪里都不明白，对不去语文老师 |
|
9
XiongZaizi OP @jmc891205 有道理呢，这样能减少很大一部分的操作量了。多谢了
|
|
10
XiongZaizi OP @whalegia 第二张图中实线是假设的棍子，这根棍子没有题目中的那么长，此时棍子接触到了点 5,3，棍子继续向下倒的时候，最先接触点 2,1，再接触点 4,2。
|
|
11
Vinty May 16, 2017
接 7l，这个值应该等于(ma-1)/(mb-1),m 是令该点在可行域内的最大整数
|
|
12
XiongZaizi OP @yangff 那这样看来只有 y=1 的点是符合要求的，说的有道理
|
|
13
XiongZaizi OP @Vinty “大概就是求一个比 a/b 小的最大的两个整数之比 x/y，x/y 有公约数，化简一下即可”，这一步是求出下一个杰出的点的吧？还有后面那个公式是咋计算的？
|
 |
14
liuminghao233 May 16, 2017 via iPhone
根本就不知道你在说什么 什么 a 点
|
|
15
Vinty May 16, 2017
@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 May 16, 2017
下一次在重合到一点时，输出离原点最近的那一点的坐标
------------------------------------------------------------------------- 这句话是要再解释清楚的 “下一次在重合到一点时”，换言之，重合 A 到这次重合中间没有再重合任何点了，下半句“那一点”指的是什么？ |
 |
17
lingo May 16, 2017
哈哈哈哈哈题目看不懂
|
|
18
XiongZaizi OP @Vinty 恩恩，谢谢了，这样也是一种方法
|
|
19
XiongZaizi OP @imn1 就是棍子在向下倒的这个过程中，会接触到点格中的点，那么假设其中有一时刻棍子和给定的能够接触到的点 a 接触了记为时刻 t1，从这一时刻起开始，棍子继续向下倒，又会接触一个新的点 b，时刻记为 t2。这 t1 和 t2 两个时刻之间，棍子没有和任何的点接触。所要求的就是从 t1 时刻开始，到棍子最终倒在横轴上这一段时间里，棍子所能接触到的所有点中，距离原点最小的一点。
|
 |
20
ZyZyZzz May 16, 2017
你直接把日语题干贴出来吧，这里有的是人懂日语
不懂的还可以去机翻 |
 |
21
GtDzx May 16, 2017
感觉就是个排序题。按极角和距离排序不就完了...
|
 |
22
hxsf May 16, 2017 via iPhone
有意思的题目。
回家电脑码字 |
|
23
imn1 May 16, 2017
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 May 16, 2017 via Android
y = 1
x = min(n), where arctan(1 / n) < arctan(y0 / x0) |
|
25
hxsf May 16, 2017
到家，开更。
最暴力的方法，算一下每个点的角坐标(θ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 May 16, 2017
@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 May 16, 2017  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 May 16, 2017
@XiongZaizi
怎么需要穷举所有点呢？ 所有的点都是已知坐标的吧？ 从最小值开始计算角度是否符合就够了 如果是要尽可能大，就从 Xn<=S0 最大值开始，只要(Xn_1<Xn && Yn_1<Yn)符合就可以结束了 |
 |
33
bumz May 16, 2017
@XiongZaizi #31 这是什么书呀
|
|
34
XiongZaizi OP @imn1 啊，有理。一时没转过弯来
|
|
35
XiongZaizi OP @bumz 基友正在看的书，我也不知道叫啥。今天偶然开始讨论起来的题目。
|
Select Language