格子指向2D平面

Question

给定2D平面中的2个点,这两个点内有多少个格点？

例如,对于A(3,3)和B(-1,-1),输出为5.点为:( - 1,-1),(0,0),(1,1),(2) ,2)和(3,3).

Answer 1

显然,"格点位于两点之内"是指(让LP代表格点)LP在两点(A和B)之间的线上.

对于某些斜率和截距数m和b,线AB的方程是y = m*x + b.对于感兴趣的情况,我们可以假设m,b是合理的,因为如果其中任何一个是不合理的,那么AB上最多只有1个LP.(证明:如果有两个或多个LP在线,它有合理的斜率,比如说e/d,有d,e整数;那么y = b + x*e/d所以在LP(X,Y)在线,d*b = d*YX*e,这是一个整数,因此b是合理的.)

在下文中,我们假设A =(u,v)和B =(w,z),其中u,w和v,z具有有理差异,并且通常写y = mx + b,其中m = e/d并且b =克/ F.

案例1. A,B都是LP:让q = gcd(uw,vz); 取d =(uw)/ q和e =(vz)/ q,很容易看出AB上有q + 1个格点.

案例2a.A是LP,B不是:如果uw = h/i且vz = j/k,则m = j*i /(h*k).令q = gcd(j*i,h*k),d = h*k/q,e = j*i/q,w'= u + d*floor((wu)/ d)并且类似地对于z' ,然后按案例1解决(u,v),(w',z').对于案例2b交换A和B.

情况3. A和B都不是LP:在通过A,B的扩展线上找到LP C之后,使用类似于案例2的算法来找到LP A'内线段AB并应用案例2.要找到A',如果m = e/d,b = g/f,请注意f*d*y = d*g + e*f*x的形式为p*x + q*y = r,这是一个简单的丢番图方程可解的C =(x,y)iff gcd(p,q)除r.

复杂性:gcd(m,n)是O(ln(min(m,n))因此,如果A,B由x,y分隔,则算法复杂度通常为O(ln(Dx))或O(ln(Dy))距离Dx,Dy.