задача на площадь многоугольника, разбить его на равные две части Опции

[Bard]

Помогите решить такую задачку...
Задано количество вершин(3<N<=50) выпуклого многоугольника. А еще заданы координаты этих вершин.
Разрезать многоугольник на две части так чтобы площади обеих частей были равными. Найти минимальную длину такого разреза.

Например:
N=4
0 0 (координат 1-й точки)
0 3 (координат 2-й точки)
4 3 (координат 3-й точки)
4 0 (координат 4-й точки)

минимальная длина разреза 3...

Спасибо всем заранее...

[Bard]

да но ведь мне нужны не только диагонали но и в том числе отрезки разбивающие стороны...

А что на счет source моей задачи это наш учитель ... В этот раз он задал нам несколько задач но некоторые из них из онлайн соревнований... нет вы не подумайте что я постил эту задачу сюда чтобы поднять там(а именно на тумисе) количество своих решенных задач... просто вот эта задачка показалась мне очень сложной поэтому я подумал что наш форум поможет мне... мне нужно только понять алго вот и все...

[Lapp]

не подумайте что я постил эту задачу сюда чтобы поднять там(а именно на тумисе) количество своих решенных задач...

Надеюсь, что ты честно говоришь.
Bard, люди думают то, что думают, и изменить это не в твоих силах. Поэтому в следующий раз говори сразу, откуда задача и зачем она тебе, во избежание недоразумений.

Алгоритм примерно такой..
Фиксируешь одну сторону и проходишь циклом по всем остальным сторонам, получая всякий раз натянутые на эти две стороны 4-угольники. Вычисляешь площади двух частей исходного многоугольника, на которые разбивает его текущий 4-угольник (S1 и S2, площадь самого 4-угольника S). Перебором добиваемся, чтобы выполнялось:
либо S1<S2 и S1+S>S2 ,
либо S1>S2 и S1<S2+S .
Это гарантирует тебе, что линия деления должна проходить через текущий 4-угольник. Теперь аналитически (зная координаты вершин) решаешь задачу на минимизацию длины секущего отрезка (как функции его конца на одной стороне) при условии равенства площадей, на которые он делит 4-угольник. Находишь и запоминаешь длину этого отрезка.

Затем переходишь к соседней стороне и повторяешь все.. Иначе говоря, двойной цикл по сторонам. Из всех полученных отрезков выбираешь минимальный.