Входные данные: Во входном файле Corusant.DAT первая строка содержит единственное натуральное число N (1 <= N <= 10000) — количество карт, которыми располагает Лукас (Звездные войны). Каждая из следующих N строк описывает отдельную карту и содержит четыре целых числа x1, y1, x2, y2 (0 <= x1 <x2 <= 30000, 0 <= y1 <y2 <= 30000). Значение (x1, y1) и (x2, y2) — координаты, в указанном порядке, левого нижнего и правого верхнего угла карты. Каждая карта имеет форму прямоугольника и ее стороны параллельны осям Декартовой системы координат. Выходные данные: В исходном файле Corusant.SOL должно содержаться целое число — общая площадь, занимаемая картами.
Как вычислить площадь пересечения двух прямоугольников — алгоритм известен. А вот как вычислить их общую площадь, если прямоугольников больше двух и, например все три прямоуголника имеют общую область?
Математическая формула: пусть у нас есть три прямоугольника А, В и С, площадь , которую они вместе покрывают будет равна SA+SB+SC-SAB-SAC-SBC+SABC — понятна.
А вот как реализовать вычисление SABC?
И какой алгоритм может реализовать вычисление для N прямоугольников?