Фарбування корівника (срібло)#10345

Фарбування корівника (срібло) (Розбір)

Спочатку розглянемо одномірний варіант задачі. Нехай на числовій прямій задано $n$ відрізків $[a_{i}, b_{i}]$ [a_i, b_i], де $0 \leq a_{i}, b_{i} \leq 1000$ 0 \le a_i, b_i \le 1000. Необхідно визначити, скількома відрізками покривається кожне ціле число на цій прямій.

Оголосимо цілочисельний масив $d p$ , ініціалізуємо його нулями. Потім для кожного відрізка $[a_{i}, b_{i}]$ [a_i, b_i] виконаємо дві операції:

d p [a_{i}] + +; d p [b_{i} + 1] - -;

dp[a_i]++; dp[b_i + 1]--;

Далі обчислимо префіксні суми в масиві $d p$ . Значення $d p [i]$ дорівнює кількості відрізків, що містять число $i$ .

Наприклад, нехай дано наступні відрізки: $[3; 7], [6; 9], [1; 4], [3; 8], [2; 5]$ [3; 7], [6; 9], [1; 4], [3; 8], [2; 5]. Ініціалізуємо масив $d p$ :

Для кожного відрізка $[a_{i}, b_{i}]$ [a_i, b_i] виконаємо дві операції: $d p [a_{i}] + +; d p [b_{i} + 1] - -$ dp[a_i]++; dp[b_i + 1]--.

Тепер розглянемо двовимірний варіант задачі. На площині задано $n$ прямокутників з координатами $(x_{1}, y_{1}) - (x_{2}, y_{2}) (0 \leq x_{1}, y_{1}, x_{2}, y_{2} \leq 1000)$ (x_1, y_1) - (x_2, y_2)~(0 \le x_1, y_1, x_2, y_2 \le 1000). Потрібно визначити, скількома прямокутниками покривається кожна клітинка площини.

Оголосимо цілочисельний двовимірний масив $d p$ , ініціалізуємо його нулями. Потім для кожного прямокутника $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2) виконаємо чотири операції:

d p [x_{1}] [y_{1}] + +; d p [x_{1}] [y_{2} + 1] - -; d p [x_{2} + 1] [y_{1}] - -; d p [x_{2} + 1] [y_{2} + 1] + +;

dp[x_1][y_1]++; dp[x_1][y_2 + 1]--; dp[x_2 + 1][y_1]--; dp[x_2 + 1][y_2 + 1]++;

Після цього обчислимо префіксні суми в масиві $d p$ . Значення $d p [i] [j]$ dp[i][j] буде дорівнювати числу прямокутників, що містять клітинку $(i, j)$ .

Розглянемо, наприклад, прямокутник $(2, 2) - (4, 5)$ (2, 2) - (4, 5).

Приклад

Розглянемо наведений приклад, що містить три прямокутники.

$k = 2$ k = 2 шарами фарби покрито $8$ квадратів.

Реалізація алгоритму

Оголосимо двовимірний масив $d p$ .

#define MAX 1001
int dp[MAX][MAX];

Читаємо вхідні дані.

scanf("%d %d", &n, &k);
while (n--)
{

Для кожного прямокутника $(a, b) - (c, d)$ (a, b) - (c, d) виконаємо чотири операції.

  scanf("%d %d %d %d", &a, &b, &c, &d);
  dp[a][b]++;
  dp[a][d]--;
  dp[c][b]--;
  dp[c][d]++;
}

В змінній $r es$ підраховуємо кількість клітинок стіни, покритих рівно $k$ шарами фарби.

res = 0;

Обчислюємо префіксні суми в масиві $d p$ .

for (i = 0; i < MAX; i++)
  for (j = 0; j < MAX; j++)
  {
    if (i) dp[i][j] += dp[i - 1][j];
    if (j) dp[i][j] += dp[i][j - 1];
    if (i && j) dp[i][j] -= dp[i - 1][j - 1];

Якщо клітинка $(i, j)$ покрита $k$ шарами фарби, то збільшуємо $r es$ на $1$ ,

    if (dp[i][j] == k) res++;
  }

Виводимо відповідь.

printf("%d\n", res);