Вот еще интересная задачка:

Есть массив Rectangle[] rects, в котором описываются прямоугольники, необходимо вычислить площадь многоугольника, образуемого наложением многоугольников из этого массива.

Ломал, ломал голову, но чтото решения подозрительно сложными и громоздкими получаются, а исходя из того что это задачка была на олимпиаде, решение по идее должно быть простым... ктото знает как решить?

Здравствуйте, Streamer1, Вы писали:

S>Вот еще интересная задачка:

S>Есть массив Rectangle[] rects, в котором описываются прямоугольники, необходимо вычислить площадь многоугольника, образуемого наложением многоугольников из этого массива.

S>Ломал, ломал голову, но чтото решения подозрительно сложными и громоздкими получаются, а исходя из того что это задачка была на олимпиаде, решение по идее должно быть простым... ктото знает как решить?

Есть простое решение за O(n^3).
Заносим все x-координаты вертикальных сторон прямоугольников в массив X, все y-координаты горизонтальных — в Y.
Сортируем массивы. Получаем "сетку".
Затем перебираем все прямоугольники, входящие в эту "сетку" (двойным циклом по массивам X и Y), для каждого из них проверяем принадлежит ли он некоторому исходному прямоугольнику. Если принадлежит, то добавляем его площадь к суммарной площади.

Здравствуйте, Streamer1, Вы писали:

S>Вот еще интересная задачка:

S>Есть массив Rectangle[] rects, в котором описываются прямоугольники, необходимо вычислить площадь многоугольника, образуемого наложением многоугольников из этого массива.

S>Ломал, ломал голову, но чтото решения подозрительно сложными и громоздкими получаются, а исходя из того что это задачка была на олимпиаде, решение по идее должно быть простым... ктото знает как решить?

ищем минимум и максимум по x и y, находим sizex = max(x)-min(x) и sizey = max(y)-min(y)
в целых числах дальше можно использовать графическое решение...
в дробных — надо установить, или посчитать коэффициент для x и y.
рисуем их в массив размером sizexXsizey (заполняем поля, где находится хотябы один из многоугольников)
пробегаемся по нему и добавляем в итоговую сумму те поля, которые заполнены.

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

Streamer1 wrote:
> Ломал, ломал голову, но чтото решения подозрительно сложными и
> громоздкими получаются, а исходя из того что это задачка была на
> олимпиаде, решение по идее должно быть простым... ктото знает как решить?
Не помню как называется алгоритм (line sweep, кажется), давно читал о
нем в книжке по вычислительной геометрии. Он достаточно простой:

Сортируем прямоугольники по X-кооридинатам левого верхнего угла и строим
карту между x-координатой-вершин и номером прямоугольника.

Затем начинаем "сканирование" плоскости вертикальной линией с левого
края (то есть идем по карте x-координат). Берем список прямоугольников,
который пересекает "сканирующую линию" (мы его построили на первом шаге)
и считаем длину их проекции на ось OY.

Запоминаем эту длину и идем к следующей точке сканирования. Умножаем
длину проекции на длину шага между точками и прибавляем к общей сумме
площади. На новой точке сканирования повторяем всю операцию.

Общая сложность будет порядка O(N*M), в худшем случае O(N*2). Еще можно
оптимизировать до O(N*log N), если считать не просто длину проекции, а
хранить список отрезков проекции.