Задача [B-A'] 2: Аккуратные распилы Условие задачи...

Question

Задача [B-A'] 2: Аккуратные распилы
Условие задачи (pdf)

На факультете геометрии одного мерзкого, флегматичного и тоскливого института хранятся иллюстрации выпуклых многоугольников, координаты вершин которых являются целыми числами. Администрация факультета считает иллюстрацию тем лучше, чем больше существует способов аккуратно распилить ее на две части.

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

Студентам в качестве экзамена была дана задача — найти количество аккуратных распилов данного выпуклого многоугольника. Разумеется, студенты мерзкого института не справились с этой задачей. Теперь ее придется решить вам.

Формат входных данных
Первая строка содержит одно целое число
n
(
4
≤
n
≤
200
000
) — количество вершин многоугольника.

Каждая из следующих
n
строк содержит два целых числа
x
i
и
y
i
(
−
10
9
≤
x
i
,
y
i
≤
10
9
) — координаты
i
-й вершины многоугольника.

Гарантируется, что многоугольник является выпуклым, а вершины перечислены в порядке его обхода по или против часовой стрелки.

Формат выходных данных
Выведите одно целое число — количество аккуратных распилов данного многоугольника.

Примеры
Входные данные
4
0 0
1 0
1 1
0 1
Выходные данные
0
Входные данные
4
0 0
2 0
2 2
0 2
Выходные данные
2
Входные данные
6
1 0
5 1
8 4
7 8
2 7
-1 3
Выходные данные
3
Примечания
В первом примере существует два распила, однако они не являются аккуратными, так как делят многоугольник на части с площадью
1
2
.

Во втором примере оба распила являются аккуратными.

Иллюстрация к третьему примеру приведена ниже. На ней показаны аккуратные распилы, а также посчитаны площади полученных многоугольников.

Answer 1

Ниже — короткое решение и линейный алгоритм.

Идея

Пусть $P$ — выпуклый многоугольник с целочисленными вершинами $v_i=(x_i,y_i)$ в порядке обхода.

Если площадь $S(P)$ нецелая (т.е. $2S(P)$ нечётна), «аккуратных распилов» нет вовсе.
Действительно, сумма двух целых площадей не может дать нецелое число.
Для диагонали $(i,j)$ (берём $i<j$ , не ребро) удвоенная площадь части, ограниченной цепочкой $i\to i\!+\!1\to\cdots\to j$ и диагональю $j\to i$ , равна

A_{ij}^{(2)}=\sum_{k=i}^{j-1}[v_k,v_{k+1}]+[v_j,v_i], \quad [a,b]=x_a y_b-y_a x_b.

Нам нужна лишь чётность $A_{ij}^{(2)}$ .

Введём префиксы по чётности

p_0=0,\quad p_{k+1}\equiv p_k+[v_k,v_{k+1}]\pmod2 \ \ (k=0,\dots,n-2).

Тогда

A_{ij}^{(2)}\equiv p_j-p_i+[v_j,v_i]\equiv p_j+p_i+[v_j,v_i]\pmod2,

и условие «площадь целая» эквивалентно

p_j \equiv p_i + ([v_i,v_j]\bmod 2).

По модулю 2 детерминант зависит только от чётностей координат:

[v_i,v_j]\bmod2 \equiv (x_i\bmod2)(y_j\bmod2)\oplus (y_i\bmod2)(x_j\bmod2).

Значит, достаточно знать для вершины её тип из четырёх: $(x\!\bmod2,y\!\bmod2)\in\{00,01,10,11\}$ .

Как посчитать за $O(n)$

Держим «хвост» допустимых $j$ для текущего $i$ : это индексы $j\in[i+2,\dots,n-1]$ (пара $(0,n-1)$ — ребро, её отдельно вычтем при $i=0$ ).
В этом хвосте считаем вершины по двум признакам: тип $\in\{0,1,2,3\}$ и значение $p_j\in\{0,1\}$ — итого таблица $4\times2$ .

Для фиксированного $i$ и типа $t$ нужные $j$ — это те, у кого $p_j = p_i \oplus det2[\text{type}(i)][t]$ , где $det2$ — заранее подготовленная таблица чётностей $[v_i,v_j]\bmod2$ для пар типов. Суммируем по всем типам $t$ соответствующие счётчики из хвоста — получаем вклад текущего $i$ . Переходим к $i+1$ : удаляем из хвоста вершину $j=i+2$ . Весь подсчёт — $O(4)$ операций на шаг, итого $O(n)$ .

Если $2S(P)$ нечётно — сразу печатаем 0.

Реализация (C++17)

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> x(n), y(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];

    auto cross2_parity = [&](int i, int j)->int {
        // [vi, vj] mod 2, в F2 вычитание = сложение
        int xi = x[i] & 1, yi = y[i] & 1;
        int xj = x[j] & 1, yj = y[j] & 1;
        return (xi & yj) ^ (yi & xj);
    };

    // Префиксы по чётности, без последнего ребра (n-1,0)
    vector<int> p(n, 0);
    for (int i = 0; i+1 < n; ++i) {
        p[i+1] = p[i] ^ cross2_parity(i, i+1);
    }
    // чётность 2*S(P)
    int total_parity = (p[n-1] ^ cross2_parity(n-1, 0));
    if (total_parity & 1) {
        cout << 0 << "\n";
        return 0;
    }

    // Тип вершины по (x mod 2, y mod 2)
    auto typeOf = [&](int i)->int {
        return ((x[i]&1) << 1) | (y[i]&1); // 0..3
    };
    int tp0 = typeOf(0);

    // Таблица det2 для пар типов
    int det2[4][4];
    for (int a = 0; a < 4; ++a) {
        int ax = (a>>1)&1, ay = a&1;
        for (int b = 0; b < 4; ++b) {
            int bx = (b>>1)&1, by = b&1;
            det2[a][b] = (ax & by) ^ (ay & bx);
        }
    }

    // Счётчики в «хвосте» j in [2..n-1]
    long long cnt[4][2] = {};
    for (int j = 2; j < n; ++j) {
        cnt[typeOf(j)][p[j]]++;
    }

    long long ans = 0;
    for (int i = 0; i < n-1; ++i) {
        int ti = typeOf(i);
        for (int t = 0; t < 4; ++t) {
            int need = p[i] ^ det2[ti][t];
            ans += cnt[t][need];
        }
        // убрать ребро (0, n-1), если сочтено
        if (i == 0) {
            int tlast = typeOf(n-1);
            if (p[n-1] == (p[0] ^ det2[tp0][tlast])) ans--;
        }
        // сдвигаем «окно»: выкидываем j = i+2
        if (i+2 < n) {
            cnt[typeOf(i+2)][p[i+2]]--;
        }
    }

    cout << ans << "\n";
    return 0;
}

Сложность

Время: $O(n)$ .
Память: $O(1)$ (фиксированные массивы $4\times 2$ и префиксный массив).

Код считает только по чётностям, поэтому нигде не переполняется (даже при $|x_i|,|y_i|\le 10^9$ ), а ответ хранится в long long.

Задача [B-A'] 2: Аккуратные распилы Условие задачи...

Pergunta

Python

Pensamento

Presenting the solution

Considering overflow and computation

Clarifying storage and computational requirements

Summarizing the solution approach

Resposta

Идея

Как посчитать за $O(n)$

Реализация (C++17)

Сложность

Pergunta

0011
2
AND
0101
2

0001
2

Compartilhar esta Q&A

Pergunta

Python

Pensamento

Presenting the solution

Considering overflow and computation

Clarifying storage and computational requirements

Summarizing the solution approach

Resposta

Идея

Как посчитать за O(n)O(n)O(n)

Реализация (C++17)

Сложность

Pergunta

0011 2 AND 0101 2

0001 2

Compartilhar esta Q&A

Как посчитать за $O(n)$

0011
2
AND
0101
2

0001
2