Задача про Художника.

Задача про Художника. Відомий художник вирішив написати новий шедевр. Після багатьох днів старанної роботи він захотів дослідити своє створіння. Художник згадав, що картина писалася наступним чином: спочатку було  взяте біле полотно, що має форму прямокутника шириною w і висотою h. Потім художник намалював на цьому полотні n прямокутників зі сторонами, паралельними сторонам полотна і вершинами, розташованими в цілочисельних координатах. Допоможіть художнику визначити площу не зафарбованої  частини полотна.

Вхідні дані.

Перший рядок вхідного файлу INPUT.TXT містить два натуральних числа w і h (1 ≤ w, h ≤ 100). У другому рядку записано ціле число n (0 ≤ n ≤ 5000) - кількість прямокутників. Наступні n рядків містять інформацію про всі  зафарбовані прямокутники. Кожен рядок описує один прямокутник у вигляді чотирьох чисел x1, y1, x2, y2, де (x1, y1) і (x2, y2) - координати лівого верхнього і правого нижнього кута прямокутника відповідно.

Вихідні дані.

Виведіть у вихідний файл OUTPUT.TXT одне ціле число - площа не зафарбованої частини полотна.

Приклад №1.  

5   5

2

1 1 3 3

2 2 4 4      

Відповідь : 18

Приклад №2.

6 7

3

0 0 5 5

1 1 4 4

2 2 3 3      

Відповідь : 18

17

Розв’язання. У цьому завданні необхідно зрозуміти, що координати зафарбованих прямокутників визначаються не координатами  середин, а координатами сітки, тобто ліва верхня координата має значення (0,0) в той час як права нижня - (W, H). Це випливає з прикладів, перший з яких представлений на малюнку справа, де видно, що дійсно 18 клітин таблиці не зафарбовані.

Дане завдання вирішується "в лоб". Можна визначити матрицю [1..n] х[1..m] і покроково зчитувати координати протилежних вершин прямокутника і відразу ж заповнювати одиницями цей прямокутник в матриці. Попередньо матрицю необхідно обнулити. По завершенні процесу можна підрахувати число нулів в матриці, це і буде відповіддю на завдання. Максимальне число простих операцій може бути дорівнює 50 000 000. Незважаючи на таке, здавалося б величезне число вирішення завдання укладається в 1 секунду. Справа в тому, що проведені операції - це заповнення елементів масиву числами, які виконуються дуже швидко. Якби стільки ж разів нам потрібно було виконати серію множень, то ми навряд чи змогли б розраховувати на успіх.

Наведемо приклад вирішення даного завдання на алгоритмічній мові:

 int a[1..100][1..100]={0...0};

  read(w,h,n);

  for i=1..n{

    read(x1,y1,x2,y2);

    for y=y1+1..y2{

      for x=x1+1..x2{

        a[y][x]=1;

      }

    }

  }

  c=0;

  for y=1..h{

    for x=1..w{

      c=c+1-a[y][x];

    }

  }

  write(c);