2D 평면의 격자 점

Question

2D 평면에서 2 점을 주면이 두 점 내에 몇 개의 격자 점이 있습니까?

예를 들어, A (3, 3) 및 B (-1, -1)의 경우 출력은 5입니다. 포인트는 (-1, -1), (0, 0),), (2, 2) 및 (3, 3).

Answer 1

분명히 "격자 점은 두 점 내에 있습니다"는 것은 LP가 두 점 (A와 B) 사이의 선상에 있음을 의미합니다 (LP 점은 격자 점을 나타냅니다).

일부 기울기와 절편 번호 m 및 b에 대해 AB의 방정식은 y = m * x + b입니다. 관심있는 경우, 우리는 m, b가 합리적이라고 가정 할 수 있습니다. 왜냐하면 비합리적인 경우 AB에 최대 1 LP가 있기 때문입니다. (증명 : 2 개 또는 그 이상의 LP가 온라인 상태이면, d/e 정수를 가진 e/d와 같은 합리적인 기울기를 가지며, y = b + x * e/d이므로 라인의 LP (X, Y) u, w와 함께 A = (u, v)와 B = (w, z)라고 가정하면 다음과 같이 나타낼 수 있습니다. v, z는 합리적인 차이가 있으며 일반적으로 y = mx + b (m = e/d 및 b = g/f)를 씁니다.

사례 1. A, B 둘 다 모두 LP입니다. Let q = gcd (u-w, v-z); d = (u-w)/q 및 e = (v-z)/q를 취하면 AB에 q + 1 개의 격자 점이 있음을 쉽게 알 수 있습니다.

사례 2a. A는 LP이고, B는 다음과 같지 않습니다. u-w = h/i이고 v-z = j/k이면 이면 m = j * i/(h * k)입니다. j = i * q, w '= u + d * floor ((wu)/d) 그리고 z'에 대해 유사하게 q = gcd (j * i, h * k) 케이스 1과 마찬가지로 (u, v), (w ', z')를 풀어 라. 케이스 2b는 A와 B를 교환한다.

사례 3. A 나 B도 LP가 아니다. A, B를 통한 확장 된 선은 사례 2에서와 같이 산술을 사용하여 LP A '내부 선분 AB를 찾고 사례 2를 적용합니다. m = e/d, b = g/f 인 경우 A'를 찾으려면 f * d * y = d * g + e * f * x는 p * x + q * y = r 형식의 간단한 Diophantine 방정식으로, C = (x, y) if gcd (p, q) 아르 자형.

복잡도 : gcd (m, n)은 O (ln (min (m, n))이므로 A, B가 분리되어 있으면 알고리즘 복잡도는 일반적으로 O (ln (Dx)) 또는 O (ln x, y 거리에 의해 Dx, Dy