Подсчитать количество вариантов - алгоритм

[denis_stell]

Добрый вечер,
обращаюсь за помощью с решением одной не стандартной задачи:
Нужен алгоритм решения
Строительная компания приобрела участок земли  прямоугольное поле размером N X M сек-
торов. После проведения геологических исследований выяснилось, что на поле есть K непригодных
для строительства секторов. Необходимо построить одно здание прямоугольной формы со сторо-
нами параллельными границам участка. Компания заинтересована в рациональном использовании
участка, поэтому границы здания должны упираться либо в непригодные для строительства секто-
ры, либо в границы участка. Сколько существует вариантов выбора места для строительства здания
на приобретенном участке?
Формат входного файла
В первой строке задаются размеры поля N, M (1 ≤ N, M ≤ 10^9) и количество непригодных
для строительства секторов K (1 ≤ K ≤ 500). В следующих K строках задаются координаты
непригодных секторов Xi, Yi (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M). Все числа во входных данных целые.
Формат выходного файла
Число вариантов выбора места для строительства здания.

[denis_stell]

Прикладываю как я сам понимаю,
например у нас участок 7*4
заштрихованные ячейки у нас непригодные ячастки.

[Abstraction]

Ваше?
Может, объясните, чем не угодило решение от ---Rt-------- ?

[denis_stell]

Сообщение от Abstraction

Ваше?
Может, объясните, чем не угодило решение от ---Rt-------- ?

моё
Rt,
написал
0) нет ни одного плохого участка : ответ = 1 (вариант)
1) добавляем первый плохой участок : ответ (в общем случае) = 4 (варианта)
2) добавляем второй плохой участок

на каждом шаге поддерживаем список получившихся зданий

Потом добавляем следующий плохой участок и смотрим как он рубит какие-то здания
из предыдущего списка зданий


У меня проблема реализации,данного алгоритма, как получившиеся здания проверять?получать?

[Abstraction]

Нужен алгоритм решения

У меня проблема реализации,данного алгоритма, как получившиеся здания проверять?получать?

Вы бы определились для начала. Алгоритм - вот он. Если есть проблема с реализацией - попробуйте уточнить, с чем именно. Список - стандартная структура данных, здание характеризуется четырьмя числами (лево-верх-право-низ), пересечение здания и участка проверяется элементарно. Единственный нюанс - надо не забыть удалять дубликаты, если они получатся. Поэтому для оптимизации по времени лучше бы самобалансирующееся дерево вместо списка, но \Вам для начала стоит реализовать список; окажется медленно - переделаете.