Перейти до основного вмісту

Цілочислові точки всередині нецілочислового многокутника

Для цілочислових многокутників існує формула Піка, яка дозволяє підрахувати кількість цілочислових точок усередині многокутника. А що робити з многокутниками, вершини яких довільні?

Коли підходить цей алгоритм?
  • Потрібно підрахувати цілочислові точки всередині многокутника з нецілочисловими (довільними) вершинами?
  • Вершини многокутника цілочислові? Тоді задача розв'язується простіше. (якщо так → Теорема Піка)
  • Готовий рахувати суму ∑⌊kx+b⌋\sum \lfloor kx + b \rfloor під кожним ребром (підхід у дусі алгоритму Евкліда) для кожного ребра окремо?

Опрацюймо кожне ребро многокутника окремо, а після цього зможемо просумувати кількості цілочислових точок під кожним ребром, враховуючи його орієнтацію для вибору знака (так само, як при обчисленні площі многокутника через трапеції).

Насамперед зауважимо, що якщо поточне ребро має кінці в точках A=(x1;y1)A=(x_1;y_1) і B=(x2;y2)B=(x_2;y_2), то його можна подати як лінійну функцію:

y=y1+(y2−y1)⋅x−x1x2−x1=(y2−y1x2−x1)⋅x+(y1x2−x1y2x2−x1)y=y_1+(y_2-y_1) \cdot \dfrac{x-x_1}{x_2-x_1}=\left(\dfrac{y_2-y_1}{x_2-x_1}\right)\cdot x + \left(\dfrac{y_1x_2-x_1y_2}{x_2-x_1}\right) y=k⋅x+b, k=y2−y1x2−x1, b=y1x2−x1y2x2−x1y = k \cdot x + b,~k = \dfrac{y_2-y_1}{x_2-x_1},~b = \dfrac{y_1x_2-x_1y_2}{x_2-x_1}

Тепер виконаємо заміну x=x′+⌈x1⌉x=x'+\lceil x_1 \rceil, так що b′=b+k⋅⌈x1⌉b' = b + k \cdot \lceil x_1 \rceil. Це дозволяє нам працювати з x1′=0x_1'=0 та x2′=x2−⌈x1⌉x_2'=x_2 - \lceil x_1 \rceil. Позначимо n=⌊x2′⌋n = \lfloor x_2' \rfloor.

Ми не сумуватимемо точки при x=nx = n і на y=0y = 0 задля цілісності алгоритму. Їх можна додати вручну згодом. Отже, нам треба просумувати ∑x′=0n−1⌊k′⋅x′+b′⌋\sum\limits_{x'=0}^{n - 1} \lfloor k' \cdot x' + b'\rfloor. Також припускаємо, що k′≥0k' \geq 0 і b′≥0b'\geq 0. Інакше слід зробити заміну x′=−tx'=-t і додати ⌈∣b′∣⌉\lceil|b'|\rceil до b′b'.

Обговорімо, як можна обчислити суму ∑x=0n−1⌊k⋅x+b⌋\sum\limits_{x=0}^{n - 1} \lfloor k \cdot x + b\rfloor. Маємо два випадки:

  • k≥1k \geq 1 або b≥1b \geq 1.

    Тоді нам слід почати із сумування точок під y=⌊k⌋⋅x+⌊b⌋y=\lfloor k \rfloor \cdot x + \lfloor b \rfloor. Їхня кількість дорівнює

    ∑x=0n−1⌊k⌋⋅x+⌊b⌋=(⌊k⌋(n−1)+2⌊b⌋)n2.\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}.

    Тепер нас цікавлять лише точки (x;y)(x;y) такі, що ⌊k⌋⋅x+⌊b⌋<y≤k⋅x+b\lfloor k \rfloor \cdot x + \lfloor b \rfloor < y \leq k\cdot x + b. Ця кількість збігається з кількістю точок таких, що 0<y≤(k−⌊k⌋)⋅x+(b−⌊b⌋)0 < y \leq (k - \lfloor k \rfloor) \cdot x + (b - \lfloor b \rfloor). Отже, ми звели нашу задачу до k′=k−⌊k⌋k'= k - \lfloor k \rfloor, b′=b−⌊b⌋b' = b - \lfloor b \rfloor, де тепер і k′k', і b′b' менші за 11. Ось малюнок: ми щойно просумували сині точки і відняли синю лінійну функцію від чорної, щоб звести задачу до менших значень kk і bb:

    Subtracting floored linear function

  • k<1k < 1 і b<1b < 1.

    Якщо ⌊k⋅n+b⌋\lfloor k \cdot n + b\rfloor дорівнює 00, ми можемо безпечно повернути 00. Якщо ж це не так, то можна стверджувати, що немає цілочислових точок таких, що x<0x < 0 і 0<y≤k⋅x+b0 < y \leq k \cdot x + b. Це означає, що ми отримаємо ту саму відповідь, якщо розглянемо нову систему відліку, у якій O′=(n;⌊k⋅n+b⌋)O'=(n;\lfloor k\cdot n + b\rfloor), вісь x′x' напрямлена вниз, а вісь y′y' напрямлена ліворуч. Для цієї системи відліку нас цікавлять цілочислові точки на множині

    {(x;y) ∣ 0≤x<⌊k⋅n+b⌋, 0<y≤x+(k⋅n+b)−⌊k⋅n+b⌋k}\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>1k>1. Нову точку відліку O′O' та осі X′X' і Y′Y' можна побачити на малюнку нижче:

    New reference and axes

    Як бачите, у новій системі відліку лінійна функція матиме коефіцієнт 1k\tfrac 1 k, а її нуль буде в точці ⌊k⋅n+b⌋−(k⋅n+b)\lfloor k\cdot n + b \rfloor-(k\cdot n+b), що робить наведену вище формулу правильною.

Аналіз складності​

Нам треба підрахувати щонайбільше (k(n−1)+2b)n2\dfrac{(k(n-1)+2b)n}{2} точок. Серед них на найпершому кроці ми підрахуємо ⌊k⌋(n−1)+2⌊b⌋2\dfrac{\lfloor k \rfloor (n-1)+2\lfloor b \rfloor}{2}. Можемо вважати, що bb є знехтувано малим, оскільки на початку ми можемо зробити його меншим за 11. У такому разі можна сказати, що ми підраховуємо приблизно ⌊k⌋k≥12\dfrac{\lfloor k \rfloor}{k} \geq \dfrac 1 2 усіх точок. Отже, ми завершимо за O(log⁡n)O(\log n) кроків.

Реалізація​

Ось проста функція, яка обчислює кількість цілочислових точок (x;y)(x;y) таких, що 0≤x<n0 \leq x < n та 0<y≤⌊kx+b⌋0 < y \leq \lfloor k x+b\rfloor:

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 — це деякий клас для роботи з раціональними числами. На практиці виявляється, що якщо всі знаменники й чисельники за абсолютною величиною не перевищують CC, то в рекурсивних викликах вони будуть не більшими за C2C^2, якщо ви постійно ділите чисельники й знаменники на їхній найбільший спільний дільник. За цього припущення можна сказати, що допустимо використовувати double і вимагати точності ε2\varepsilon^2, де ε\varepsilon — це точність, з якою задано kk і bb. Це означає, що під час заокруглення вниз числа слід вважати цілими, якщо вони відрізняються від цілого не більш ніж на ε2\varepsilon^2.