Помощь - Поиск - Пользователи - Календарь
Полная версия: задача на площадь многоугольника
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Bard
Помогите решить такую задачку... smile.gif
Задано количество вершин(3<N<=50) выпуклого многоугольника. А еще заданы координаты этих вершин.
Разрезать многоугольник на две части так чтобы площади обеих частей были равными. Найти минимальную длину такого разреза.

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

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

Спасибо всем заранее... smile.gif
fox
Цитата(Bard @ 3.06.2007 10:43) *

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

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


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

Еще одно подобное сообщение и пеняй на себя. Нечего сказать по делу ? Промолчи.
Bard
Цитата
решить можно через массиввы
по моему smile.gif

да спасибо за помощь но через массивы можно решить любую задачу... good.gif
Bard
помогите мне пожалуйста с реализацией алгоритма...
мисс_граффити
вот формула для вычисления площади:
http://algolist.manual.ru/maths/geom/polygon/area.php

сам алгоритм... ничего умнее полного перебора не придумывается sad.gif
брать 3, 4, 5...25 точек, пока не найдем многоугольник, площадь которого равна 1/2 данного
Bard
На самом деле я думаю что мне надо просто найти те точки через которые будет проходить этот отрезок mega_chok.gif ...
А как это перебором? Все точки находящиеся на сторонах многоуголбника что-ли? nea.gif blink.gif
Michael_Rybak
Оффтоп: А зачем тебе эта задача, если не секрет?

Онтоп: перебор подходит или не подходит в зависимости от требуемой точности ответа.
мисс_граффити
Я почему-то прочитала, что разрезать по вершинам.
С произвольными точками перебор точного ответа не даст... sad.gif Или точки обязаны иметь целочисленные координаты?
Lapp
Цитата(Michael_Rybak @ 4.06.2007 22:30) *
Оффтоп: А зачем тебе эта задача, если не секрет?
Да, Bard, мне тоже интересно - вам такие задают?

Цитата(Michael_Rybak @ 4.06.2007 22:30) *
перебор подходит или не подходит в зависимости от требуемой точности ответа.
Осмелюсь поперечить.. А кто сказал, что перебор по вершинам? Перебор с делением четырехугольника на части - рулит! smile.gif

Цитата(мисс_граффити @ 5.06.2007 0:08) *
Я почему-то прочитала, что разрезать по вершинам.
Не играет роли. Просто добавь к этому перебору деление центрального четырехугольника и скажи, что это и имела в виду rolleyes.gif.

Цитата(Bard @ 4.06.2007 16:39) *
А как это перебором? Все точки находящиеся на сторонах многоуголбника что-ли?
Нет, сторону дели из соображений нужной пропорции и минимальности длины отрезка для выбранной пары сторон.
Michael_Rybak
>А кто сказал, что перебор по вершинам?

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

Вот это последнее можно сделать аналитически, а можно перебором - одну из сторон поделить на маленькие отрезочки smile.gif
Lapp
Цитата(Michael_Rybak @ 5.06.2007 12:56) *

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

Метод последовательных приближений - не есть перебор! smile.gif Этак можно договориться, что деление чисел "уголком" - тоже перебор.. Да и вообще, вся теория чисел - сплошной перебор (во всех смыслах smile.gif).
Сорри за оффтоп..
Bard
Извините что вмешиваюсь smile.gif но о каком переборе идет речь(ну тоесть о переборе чего-углов или сторон?) ? blink.gif
Lapp
Для начала, перебор всех диагоналей. Таким образом находишь те диагонали, которые делят на "наиболее равные" части. Затем пляшешь вокруг них (уже аналитически).

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

А что на счет source моей задачи это наш учитель smile.gif ... В этот раз он задал нам несколько задач но некоторые из них из онлайн соревнований... нет вы не подумайте что я постил эту задачу сюда чтобы поднять там(а именно на тумисе) количество своих решенных задач... просто вот эта задачка показалась мне очень сложной поэтому я подумал что наш форум поможет мне... мне нужно только понять алго вот и все... smile.gif
Michael_Rybak
Продолжая за Lapp'a: смотри, концы искомого отрезка будут лежать на двух каких-то сторонах многоугольника. Двумя вложенными циклами перебираем эти вот две стороны, и получаем подзадачу для четырехугольника (только его уже надо не на равные площади делить; а как?). Вот в этом направлении думай.
Lapp
Цитата(Bard @ 6.06.2007 1:43) *

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

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

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



а еще что это означает blink.gif ?
Цитата
Перебором добиваемся, чтобы выполнялось:

каким перебором - по углам? wink.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.