Размещение треугольников на линии, минимизируя наибольшее расстояние - PullRequest
Новая
       13

Размещение треугольников на линии, минимизируя наибольшее расстояние

0 голосов
/ 08 февраля 2019

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

Я могу вращать треугольники, но не могуизмените их размер или форму.

Я пытался расположить треугольники, вроде круга, вокруг одной точки линии, пока не будет достигнут угол 180 °, и повторил процесс, но мне не кажется, что это очень эффективно.алгоритм.

Example (non-altered)

1 Ответ

0 голосов
/ 09 февраля 2019

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

Во-вторых, сортируйте треугольники по углу нижнего правого угла и собирайте их в указанном порядке.После этого они не будут пересекаться.

Доказательство второго шага 

   B          D
   |\        /|
   | \      / |
   |  \    /  |
   |   \  /   |
   |____\/____|
   A    C     E

Для отсортированных треугольников ACB DCE <180 - CED ACB <CED и DCE <180 - CED -> ACE + DCE <180, поэтому треугольники не будут перекрываться. </p>

...