eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Площадь покрытия

Площадь покрытия

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

Входные данные

Первая строка содержит количество тестов, не более 100. Далее для каждого теста:

  • в первой строке находится количество фотографий n (1n1000).

  • n строк с четырьмя целыми числами x[1], y[1], x[2] и y[2] (0x[1], y[1], x[2], y[2]10^6, x[1] < x[2] и y[1] < y[2]): координаты юго-западного и северо-восточного угла соответственно для каждой фотографии. Фотографии имеют прямоугольную форму с углами (x[1], y[2]) и (x[2], y[1]).

Координаты соответствуют двумерной плоскости (считаем, что Земля плоская).

Выходные данные

Для каждого теста вывести в отдельной строке общую площадь сфотографированного пространства.

prb6406.gif

Пример

Входные данные #1
2
3
1 2 7 5
3 0 4 7
6 4 8 8
2
1 1 4 5
2 2 7 4
Выходные данные #1
29
18
Источник 2013 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Сентябрь 28, Задача A