Доброго всем времени суток!!!
На универской олимпиаде по программированию попалась интересная задачка. А интересная тем, что НИКТО ее не сделал. Ее текст


В общем идея-то у меня есть. Использую аналитическую геометрию. Т.е. 
1. я могу написать нормальное уравнение прямой сгиба. 
2. Потом найти координаты точек углов относительно это прямой (осевая симметрия относительно прямой сгиба)
3. В зависимости от того, куда эти точки попадают, рассмотреть один из 6 (если я правильно посчитал) случаев расположения (с учетом симметрии) т.е. прямая под углом > 90 градусов

Но мне что-то не нравится: в вобщем, решаемо, но как-то коряво и слишком сложно. 
Это есть очевидно (для меня) решение. Но чувствую, что существует более красивое. 

Может, кто подобные задачи решал? 
P.S.  Не удивлюсь, если им окажется maxim1000   

Заранее спасибо

Это сообщение отредактировал(а) Kuvaldis - 11.9.2006, 02:54

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

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

для больших многоугольников это может потребовать немало памяти (в зависимости от удачности выбора разбиения), но для прямоугольника начальное количество треугольников - 2, при каждом отсечении оно, как максимум, удваивается, так что в конце их будет точно меньше 16...

Добавлено @ 11:31 
совсем забыл в предыдущем алгоритме ещё надо поделить площадь на 2
вот ещё один способ придумался:
1. выбираем середину отрезка сгиба
2. пускаем из неё лучи (точнее отрезки) во все точки, которые образовывают многоугольник пересечения:
- вершины одного прямоугольника, лежащие в другом
- точки пересечения сторон прямоугольников
3. упорядочиваем их по, например, часовой стрелке
4. считаем сумму площадей получившихся треугольников (соседние отрезки будут составлять две их стороны, а третья нам и не нужна)

но у этого способа есть недосаток:
он пришёл в голову не первым...

да и вообще, все эти способы крутятся относительно способов разбиения области перечения на треугольники, можно вообще упорядочить его вершины по какой-нибудь координате и считать сумму площадей трапеций и треугольников (только там надо следить за знаками - кое-где могут быть минусы)

maxim1000, 
к сожалению, вы не очень внимательно прочитали условие 
Т.е. нужна не площадь пересечения, а площадь объединения. Хотя Ваш второй вариант решения задачи я обязательно возьму на вооружение (изящен и прост).

P.S. 
Час назад спросил про вариант решения тренера по программированию. Он сказал, что решал, как я предлагал, лишь у меня 6 вариантов расположения проеций вершин, а у него 4. (но это даже для него заняло много времени - 1.5 часа)


Это сообщение отредактировал(а) Kuvaldis - 15.9.2006, 19:53

А... действительно...
ну так можно взять всю площадь прямоугольника и отнять прощадь перекрытия