|
Название: Уменьшить 8-угольник Отправлено: Igors от Январь 17, 2012, 19:44 Добрый день
Условия задачи похожи на предыдущие http://www.prog.org.ruindex.php?topic=20586.msg140403#msg140403 (http://www.prog.org.ruindex.php?topic=20586.msg140403#msg140403) На плоскости есть выпуклый 8-угольник с центром в точке (0, 0). Дается точка p внутри 8-угольника. Задача: уменьшить 8-угольник таким образом чтобы - точка p лежала на одном из его ребер (или в вершине) - 8-угольник оставался конвексным (выпуклым) - "потери площади" от уменьшения были минимальны Пример: пусть точки 8-угольника лежат "по сторонам света" и точка p находится на "северо-западе". Тогда нужно подтянуть к центру точки: северо-запад,, север и/или запад (но не трогать юг и восток) Общая задача (зачем это нужно): заполнить поверхность 8-угольниками, которые могут перекрываться но центр одного не лежит внутри другого. Поэтому не требуется строго доказывать что новый 8-угольник "абсолютно оптимальный", нужен инженерный алгоритм который работал бы максимально быстро. Также не стоит делать предположений что точки 8-углоьника равноудалены от центра, в отдельных случаях расстояния могут отличаться в 5-10 раз Спасибо |