Ось с прямоугольниками, найти общую площадь

[sp.caster]

Дана ось на которой множество прямоугольников, найти площадь фигуры образованной ими. Для ясности вот картинка, толстой линией выделена интересующая фигура http://pikucha.ru/i4NK2

Картинка примерна и на практике в программе прямоугольники могут быть в разном количестве, размере и месте

[Serge_Bliznykov]

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

Добавлено
а ещё можно решить задачу "в лоб":
выбрать минимальный шаг - и находить максимальную величину в каждом Xi
Площадь := Сумма всех произведений по i ( deltaX * ВысотаВточкеXi )


Добавлено
ну и рисунок Вы выложили! Целое эпическое полотно!!
позволю себе продублировать его в своём сообщении (немножко подрезав, разумеется!)

[sp.caster]

спасибо конечно за редакцию рисунка) по поводу "в лоб":
то есть найти минимальный шаг? что за максимальная величина в каждом xi?

Хотя приглядевшись первый метод показался более понятным, трудность теперь в одном, закодить

[Serge_Bliznykov]

то есть найти минимальный шаг? что за максимальная величина в каждом xi?

минимальный шаг - это тот шаг (он же дельта X, он же приращение по оси X), который нам гарантирует, что изменяя координату X мы попадём точно в каждую границу.
Искать его прийдётся действительно по значения координат - прийдётся выделить в каком минимальном десятичном разряде координат есть значимая величина.
Кстати, если координаты целочисленные, то шаг можно всегда брать равным единице и не морочиться!
Если же координаты вещественные, то шаг должен быть не больше, чем единичка в наименьшем значащем разряде.
Ну, если даны координаты вертикальных сторон:
10, 12.5, 22.75, 25.1, 75.578, 100
то, очевидно, что наименьших значимый разряд - это тысячные (координата 75.578) и шаг должен быть 0.001

Кстати, если координаты представлены действительными числами, то можно подойти и с другой стороны. Взять заведомо малый шаг. Тогда, в худшем случае, получится не точное, а приближённое значение площади. но, с другой стороны - использование вещественных (действительных) чисел уже само по себе предполагает возможность отклонений (погрешности).

что за максимальная величина в каждом xi?

допустим, у нас есть какая-то координата X
тогда, перебрав в цикле все прямоугольники, у которых координата левой стороны <=X и, одновременное, координата правой стороны >=X мы можем получить все высоты прямоугольников в данной точке. Очевидно, что нас интересует максимальное значение высоты (это будет самый высокий прямоугольник, перекрывающий остальные прямоугольники в данной точке). Вот эту высоту и надо умножать на шаг приращения. Получим площать маленького вертикального прямоугольничка.
А вообще, этот способ мне наявело графическим смыслом определённого интеграла (см. например, википедию)

Хотя приглядевшись первый метод показался более понятным, трудность теперь в одном, закодить

согласен. первый способ более "честный"!
Успехов в реализации.

[sp.caster]

Спасибо огромное, а как задать в программе некое случайное количество прямоугольников случайных размеров и в случайном месте? Полагаю начинать мне надо именно с этого)

м-м-м, снимаю вопрос, т.к. предположу что есть входной файл с числом прямоугольников и соответственно координатами левого верхнего и правого нижнего угла прямоугольников

[sp.caster]

как перебирать прямоугольники? что-то блин ничего у меня не получается

[Serge_Bliznykov]

как перебирать прямоугольники?

ну, у Вас же есть структура, где храняться координаты? (Массив, например)... вот в цикле и перебирать... только сначала отсортировать по левым границам.

[sp.caster]

Для меня проблема закодить, а не в понимании... Я представляю вроде как осуществить решение, нужно составить каким-то неведомым для меня образом массив из 3 значений, (x, н (или к), h), где х - координата новой стороны очередного прямоугольника, н и к, начало или конец этой стороны соответственно, а h - высота. Далее, перебирая значения по х и учитывая высоту, суммируем по частям площади прямоугольников. Проблема перевести в код=(

[sp.caster]

фак, завтра сдавать

[Mad_Cat]

фак, завтра сдавать

тут помогут