作业帮 > 数学 > 作业

怎么计算连线穿过了多少个格子

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/13 00:29:07
怎么计算连线穿过了多少个格子
如图
对于一个标准的正方形方格组成的图
任意指定两个格子
怎么快速计算这两个格子的中心的连线穿过了多少个格子
(与格子相切不算穿过了格子,就是说如果连线穿过格子的角是不算的)
不妨将绿格子左下角视为原点,设这时红格子左下角的相对坐标为(a,b).
从绿格子中心(1/2, 1/2)到红格子中心(a+1/2, b+1/2)的连线总共要穿过a+b条坐标线,每进入一个格子就要穿过一条坐标线,所以如果不过格点的话,就会穿过a+b-1个格子(-1是因为最后一次是穿入红格子,不计).每穿过一个格点,就会漏掉一个格子,所以问题转化成计算连线穿过的格点数).
连线上任一有理点的坐标为(1/2, 1/2)(1-p/q)+(a+1/2, b+1/2)p/q, 这里0