Версия для печати темы

Автор: Bard 3.06.2007 14:43

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

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

Автор: fox 3.06.2007 14:45

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

Автор: klem4 3.06.2007 14:54

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

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

Автор: Bard 3.06.2007 15:03

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

Автор: Bard 3.06.2007 19:49

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

Автор: мисс_граффити 3.06.2007 19:57

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

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

Автор: Bard 4.06.2007 19:39

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

Автор: Michael_Rybak 5.06.2007 1:30

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

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

Автор: мисс_граффити 5.06.2007 3:08

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

Автор: Lapp 5.06.2007 7:30

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

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

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

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

Автор: Michael_Rybak 5.06.2007 15:56

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

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

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

Автор: Lapp 6.06.2007 1:30

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

Автор: Bard 6.06.2007 2:14

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

Автор: Lapp 6.06.2007 3:05

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

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

Автор: Bard 6.06.2007 4:43

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

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

Автор: Michael_Rybak 6.06.2007 5:25

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

Автор: Lapp 6.06.2007 5:28

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

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

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

Автор: Bard 7.06.2007 1:45

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

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

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