Добрый день
Условия задачи похожи на предыдущие
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 раз
Спасибо
