Пожалуйста! Помогите! Построить такой многогранник (не обязательно выпуклый) с вершинами в заданном на плоскости множестве точек, периметр которого максимален. Результат представить в графическом виде на экране. Очень надо! Пожалуйста! Мне нужен только текст!
Вопрос ! 1) А множество точек ты сам задаешь или оно выбрасываетря случайным образом ? 2) Тебе на каком языке ?
М-да, задачка какая-то олимпиадная, так сразу и не сообразишь. Если и писать прогу то текст будет давольно длинный, и придется вспомнить геометрию. Паскаль я к сожалению не не знаю, а если бы и знал то писать врятли стал бы (да и врятли кто-то другой подорвется). Но общий подход к решению я в течение следующего часа попробую набросать, хотя не обещаю (не Лобачевский)
Мне бы что-нибудь! нам раздали по 5 задач! Я могу другую предложить, но остальные в реале какие-то левые!
Например: Найти такую расстановку двенадцати коней на шахматной доске, при которой каждое поле находится под ударом одного из них. Один из вариантов расстановки представить на экране в графической форме. брррр ... это хуже, чем с ферзями! Или: «Задача о рюкзаке». Имеется М различных предметов, известны вес каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы общий вес не превышал заданной границы, а общая стоимость была максимальной. Решить эту задачу для М предметов, веса которых в килограммах равны Р1, Р2, …, Рм, стоимости - С1, С2, …, См. Вес рюкзака не должен превышать 50 килограммов. ну не маразм ли?! А мне это надо сделать на завтра! Вот сижу и матыжу! Думаю спать нынче не буду!
Может быть я ошибаюсь, но кажется решение такое: 1) Строишь выпуклый многоугольник по крайним точкам так, чтобы все остальные точки оказались внутри него. 2) Выбираешь одну из осей координат и последовательно преребираешь все точки внутри многоугольника вдоль нее. 3)Строишь треугольники у которых одна вершина лежит внутри многоугольника, а две другие являются вершинами нашего выпуклого многоугольника. Отбрасываешь все треугольники внутри которых оказалась точка из множества, а среди остальных выбираешь тот у которого сумма длинн лучей исходящих из вершины находящейся внутри изначального многоугольника наибольшая. 4) Удаляешь грань которая соединяла две вершины изначального многоугольника и получаешь новый многоугольник уже не выпуклый, но у которого сумма длинн сторон увеличилась максимально и все точки по прежнему лежат внутри вновь полученного многоугольника. 5) Повторяешь 3-ю и 4-ю итерацию до тех пор пока не избавишься от последней точки внутри многоугольника. Придется вспомнить уравнение прямой и еще кое-что из курса школьной геометрии. Выбросить N случайных точек програмно труда не составляет, необходимо будет создать массив точек, и придумать как ты будешь отличать точки внутри многоугольника, а также запоминать какая точка с какой соеденена отрезком. Ну может я и где-то просчитался и не прав в корне, но я честно старался помочь.