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

[Bard]

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

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

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

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

[fox]

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

решить можно через массиввы
по моему

[klem4]

решить можно через массиввы
по моему smile.gif

Сильно ты ему помог, сам-то как думаешь ?

Еще одно подобное сообщение и пеняй на себя. Нечего сказать по делу ? Промолчи.

[Bard]

решить можно через массиввы
по моему

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

[Bard]

помогите мне пожалуйста с реализацией алгоритма...

[мисс_граффити]

вот формула для вычисления площади:
http://algolist.manual.ru/maths/geom/polygon/area.php

сам алгоритм... ничего умнее полного перебора не придумывается
брать 3, 4, 5...25 точек, пока не найдем многоугольник, площадь которого равна 1/2 данного

[Bard]

На самом деле я думаю что мне надо просто найти те точки через которые будет проходить этот отрезок ...
А как это перебором? Все точки находящиеся на сторонах многоуголбника что-ли?

[Michael_Rybak]

Оффтоп: А зачем тебе эта задача, если не секрет?

Онтоп: перебор подходит или не подходит в зависимости от требуемой точности ответа.

[мисс_граффити]

Я почему-то прочитала, что разрезать по вершинам.
С произвольными точками перебор точного ответа не даст... Или точки обязаны иметь целочисленные координаты?

[Lapp]

Оффтоп: А зачем тебе эта задача, если не секрет?

Да, Bard, мне тоже интересно - вам такие задают?

перебор подходит или не подходит в зависимости от требуемой точности ответа.

Осмелюсь поперечить.. А кто сказал, что перебор по вершинам? Перебор с делением четырехугольника на части - рулит!

Я почему-то прочитала, что разрезать по вершинам.

Не играет роли. Просто добавь к этому перебору деление центрального четырехугольника и скажи, что это и имела в виду .

А как это перебором? Все точки находящиеся на сторонах многоуголбника что-ли?

Нет, сторону дели из соображений нужной пропорции и минимальности длины отрезка для выбранной пары сторон.

[Michael_Rybak]

>А кто сказал, что перебор по вершинам?

>Нет, сторону дели из соображений нужной пропорции и минимальности длины отрезка для выбранной пары сторон.

Вот это последнее можно сделать аналитически, а можно перебором - одну из сторон поделить на маленькие отрезочки

[Lapp]

Вот это последнее можно сделать аналитически, а можно перебором - одну из сторон поделить на маленькие отрезочки

Метод последовательных приближений - не есть перебор! Этак можно договориться, что деление чисел "уголком" - тоже перебор.. Да и вообще, вся теория чисел - сплошной перебор (во всех смыслах ).
Сорри за оффтоп..

[Bard]

Извините что вмешиваюсь но о каком переборе идет речь(ну тоесть о переборе чего-углов или сторон?) ?

[Lapp]

Для начала, перебор всех диагоналей. Таким образом находишь те диагонали, которые делят на "наиболее равные" части. Затем пляшешь вокруг них (уже аналитически).

Bard, еще раз спрашиваю - откуда у тебя эта задача? Ответь, пожалуйста.

[Bard]

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

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

[Michael_Rybak]

Продолжая за Lapp'a: смотри, концы искомого отрезка будут лежать на двух каких-то сторонах многоугольника. Двумя вложенными циклами перебираем эти вот две стороны, и получаем подзадачу для четырехугольника (только его уже надо не на равные площади делить; а как?). Вот в этом направлении думай.

[Lapp]

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

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

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

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

[Bard]

Большое спасибо ,Lapp, но я не совсем понял первую часть твоего алгоритма можешь обьяснить ее по подробнее или же если тебя не затруднит покажи мне код(паскалевский) вот этой части твоего алго:

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

а еще что это означает ?

Перебором добиваемся, чтобы выполнялось:

каким перебором - по углам?