Всем доброго времени суток!

Помогите, пожалуйста, придумать алгоритм решения следующей геометрической задачи.

Треугольник задан на плоскости координатами своих вершин: (X1, Y1), (X2, Y2), (X3, Y3). Найти длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник так, чтобы все вершины треугольника находились внутри квадрата либо на его сторонах. Составьте программу, которая по координатам вершин треугольника находит длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник. L достаточно найти с точностью 10^(-4), т.е. 0.0001.


Это сообщение отредактировал(а) V_A_KeRneL - 18.12.2006, 20:06

обсуждали мы как-то темку похожую: http://forum.vingrad.ru/topic-21917.html
там были разговоры про минимальный прямоугольник и разные критерии этой "минимальности"
если я не ошибаюсь эта задача может быть сформулирована так же, если за критерий взять длину бОльшей стороны прямоугольника...

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

Затем вращаешь треугольник вокруг начала координат, и в зависимости от угла поворота ищешь минимальное ребро описывающего квадрата со сторонами, параллельными осям координат (сторона квадрата - максимум из модулей разностей крайних точек по абсциссе и ординате)
Вероятно, проще будет выделить случаи (диапазоны по углу), когда, например, точка A - правее всех, а B - выше и так далее

Это сообщение отредактировал(а) MBo - 18.12.2006, 15:12

Не правда. Перебор не сканает.
Задача наоптимизацию. Решать через производную.

SoWa,  а где упоминался перебор?

Не оно?

2moderators: измените, пожалуйста, описание темы с «Квадрат, вписанный в треугольник» на «Треугольник, вписанный в квадрат». Обозвал неправильно по невнимательности, извиняюсь.

З.Ы. Спасибо.))


Это сообщение отредактировал(а) V.A.KeRneL - 20.1.2007, 04:17

Здорово! Курсач горит? Или опять с олимпиадными развлекаешься?   

Нетрудно доказать, что вершина треугольника на пересечении 2 более длинных сторон должна совпадать с вершиной квадрата, а остальные вершины треугольника - лежать на его сторонах. Либо длиннейшая сторона треугольника = диагонали квадрата (при этом угол между длинной и короткой сторонами будет не более 45 градусов).

Подход:

Проверяем угол между длинной и короткой сторонами. Если он не более 45 градусов - диагональ квадрата = длинной стороне треугольника.
Иначе смещаем треугольник так, чтобы вершина на пересечении длиннейших сторон легла в начало координат. Потом вращаем треугольник до тех пор, пока X одной вершины не станет равен Y второй вершины, их значения = длине стороны квадрата. 

Dixi

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

З.Ы. Сказал бы лучше, что нибудь по теме, а то так просто оффтопик получился!