Можно сначала:
1. Собрать в 1-й массив ординаты левой-верхней точки, правой-нижней точек, всех квадратов.
2. Отсортировать их по возрастанию.
3. Собрать в 2-й массив абсциссы левой-верхней точки, правой-нижней точек, всех квадратов. Этот массив должен состоять из записи типа [абсцисса, является_левой_или_правой, ордината_нижней_стороны_квадрата, ордината_верхней_стороны_квадрата]
4. Отсортировать 2-й массив по возрастанию значения абсциссы. Потом разбить плоскость на горизонтальные куски (между двумя "соседними по массиву" ординатами). И вычислить площадь каждого такого куска.
Площадь куска вычисляется так:
Для каждого горизонтального куска:
- Определяем все квадраты, части которых которые содержатся в куске. Для этого перебираем все абсциссы и отфильтровываем те, у которых сохраненные в массиве ординаты верхней и нижней сторон квадрата влазиют в рамки куска.
- Для оставшихся абсцисс используем след. алгоритм (см. нижнюю часть рисунка, двигаться слева-направо).
Code
Открытые = 0;
XСтартовая = 0;
Площадь = 0;
ВысотаКуска = ...;
Для (X in ОтфильтрованныйМассивАбсцисс) {
Если (ЯвляетсяАбсциссойЛевойСтороныКвадрата(X)) {
Если (Открытые == 0) {
XСтартовая = X;
}
Открытые++;
}
Иначе {
Открытые--;
Если (Открытые == 0) {
Площадь += ВысотаКуска*(X-XСтартовая);
}
}
}
кодик на JS во вложении. вроде щитает. проверок входных данных нету. говнокодик?)
