격자 다각형이 아닌 다각형 내부의 격자점¶
격자 다각형의 경우, 다각형 내부의 격자점을 셀 수 있는 픽의 공식이 있습니다. 그렇다면 임의의 정점을 가진 다각형은 어떻습니까?
다각형의 각 간선을 개별적으로 처리한 다음, 각 간선의 방향을 고려하여 부호를 정하고 각 간선 아래에 있는 격자점의 개수를 합산해 봅시다(사다리꼴을 이용해 다각형의 넓이를 계산하는 것과 같은 방식입니다).
우선 현재 간선의 끝점이 $A=(x_1;y_1)$과 $B=(x_2;y_2)$이면, 이 간선을 다음과 같은 일차 함수로 나타낼 수 있다는 점에 주목해야 합니다:
이제 $x=x'+\lceil x_1 \rceil$로 치환하여 $b' = b + k \cdot \lceil x_1 \rceil$이 되도록 하겠습니다. 이렇게 하면 $x_1'=0$과 $x_2'=x_2 - \lceil x_1 \rceil$을 가지고 작업할 수 있습니다. $n = \lfloor x_2' \rfloor$이라고 둡시다.
알고리즘의 일관성을 위해 $x = n$에 있는 점과 $y = 0$ 위에 있는 점은 합산하지 않겠습니다. 이 점들은 나중에 따로 더할 수 있습니다. 따라서 $\sum\limits_{x'=0}^{n - 1} \lfloor k' \cdot x' + b'\rfloor$를 합산해야 합니다. 또한 $k' \geq 0$이고 $b'\geq 0$이라고 가정합니다. 그렇지 않은 경우에는 $x'=-t$로 치환하고 $b'$에 $\lceil|b'|\rceil$을 더해야 합니다.
합 $\sum\limits_{x=0}^{n - 1} \lfloor k \cdot x + b\rfloor$를 어떻게 계산할 수 있는지 논의해 봅시다. 두 가지 경우가 있습니다:
-
$k \geq 1$ 또는 $b \geq 1$인 경우.
이 경우 먼저 $y=\lfloor k \rfloor \cdot x + \lfloor b \rfloor$ 아래에 있는 점들을 합산하는 것부터 시작해야 합니다. 그 개수는 다음과 같습니다
$$ \sum\limits_{x=0}^{n - 1} \lfloor k \rfloor \cdot x + \lfloor b \rfloor=\dfrac{(\lfloor k \rfloor(n-1)+2\lfloor b \rfloor) n}{2}. $$이제 $\lfloor k \rfloor \cdot x + \lfloor b \rfloor < y \leq k\cdot x + b$를 만족하는 점 $(x;y)$에만 관심이 있습니다. 이 개수는 $0 < y \leq (k - \lfloor k \rfloor) \cdot x + (b - \lfloor b \rfloor)$를 만족하는 점의 개수와 같습니다. 따라서 문제를 $k'= k - \lfloor k \rfloor$, $b' = b - \lfloor b \rfloor$인 경우로 축소하였으며, 이제 $k'$과 $b'$ 모두 $1$보다 작습니다. 다음 그림에서 우리는 파란색 점들을 합산하고 검은색 일차 함수에서 파란색 일차 함수를 빼서, 문제를 $k$와 $b$가 더 작은 값인 경우로 축소하였습니다:
-
$k < 1$이고 $b < 1$인 경우.
$\lfloor k \cdot n + b\rfloor$가 $0$과 같다면 안전하게 $0$을 반환할 수 있습니다. 그렇지 않은 경우, $x < 0$이고 $0 < y \leq k \cdot x + b$를 만족하는 격자점은 존재하지 않는다고 말할 수 있습니다. 즉, $O'=(n;\lfloor k\cdot n + b\rfloor)$을 원점으로 하고 $x'$축은 아래쪽을, $y'$축은 왼쪽을 향하는 새로운 좌표계를 고려해도 같은 답을 얻습니다. 이 좌표계에서 우리가 관심을 두는 것은 다음 집합 위의 격자점입니다
$$ \left\{(x;y)~\bigg|~0 \leq x < \lfloor k \cdot n + b\rfloor,~ 0 < y \leq \dfrac{x+(k\cdot n+b)-\lfloor k\cdot n + b \rfloor}{k}\right\} $$이는 다시 $k>1$인 경우로 돌아가게 합니다. 아래 그림에서 새로운 기준점 $O'$과 축 $X'$ 및 $Y'$을 확인할 수 있습니다:
보시다시피 새로운 좌표계에서 일차 함수의 계수는 $\tfrac 1 k$가 되고 그 영점은 $\lfloor k\cdot n + b \rfloor-(k\cdot n+b)$ 지점에 있게 되므로, 위의 공식이 올바르게 성립합니다.
복잡도 분석¶
최대 $\dfrac{(k(n-1)+2b)n}{2}$개의 점을 세어야 합니다. 그중 $\dfrac{\lfloor k \rfloor (n-1)+2\lfloor b \rfloor}{2}$개는 맨 첫 단계에서 세게 됩니다. 처음에 $b$를 $1$보다 작게 만드는 것으로 시작할 수 있으므로, $b$는 무시할 수 있을 만큼 작다고 간주해도 됩니다. 그 경우 전체 점 중 약 $\dfrac{\lfloor k \rfloor}{k} \geq \dfrac 1 2$만큼을 센다고 말할 수 있습니다. 따라서 $O(\log n)$단계 안에 끝나게 됩니다.
구현¶
다음은 $0 \leq x < n$이고 $0 < y \leq \lfloor k x+b\rfloor$를 만족하는 정수 점 $(x;y)$의 개수를 계산하는 간단한 함수입니다:
int count_lattices(Fraction k, Fraction b, long long n) {
auto fk = k.floor();
auto fb = b.floor();
auto cnt = 0LL;
if (k >= 1 || b >= 1) {
cnt += (fk * (n - 1) + 2 * fb) * n / 2;
k -= fk;
b -= fb;
}
auto t = k * n + b;
auto ft = t.floor();
if (ft >= 1) {
cnt += count_lattices(1 / k, (t - t.floor()) / k, t.floor());
}
return cnt;
}
여기서 Fraction은 유리수를 다루는 어떤 클래스입니다. 실제로는 모든 분모와 분자의 절댓값이 최대 $C$일 때, 분자와 분모를 계속 최대공약수로 나누어 주면 재귀 호출에서 이 값들이 최대 $C^2$가 되는 것으로 보입니다. 이 가정하에 double을 사용해도 되며, $k$와 $b$가 주어지는 정확도를 $\varepsilon$이라 할 때 $\varepsilon^2$의 정확도가 필요하다고 말할 수 있습니다. 즉, floor를 계산할 때 어떤 수가 정수와 최대 $\varepsilon^2$만큼 차이 나면 그 수를 정수로 간주해야 합니다.