2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Помогите с курсовой...
Сообщение24.11.2006, 04:48 


24/11/06
3
Москва
Вообщем программа. Можно на С, можно на Ruby. На плоскости задан треугольник координатами своих вершин. Нужно посчитать минимальную длинну стороны квадрата, в который можно вписать этот треугольник. Была идея, что решение как-то связанно с окружность описанно вокруг треугольника...но вот дальше ничего не понятно. :)
Зарание спасибо!

 Профиль  
                  
 
 
Сообщение24.11.2006, 05:04 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Очень трогательное задание. Начните с математики: найти наименьший квадрат, в которй можно вписать данный треугольник.

Попробуйте пойти по простому пути (который, к тому же, даст Вам материал для проверки программы): разберите случаи равностороннего треугольника, равнобедренного треугольника, прямоугольного треугольника.

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

Быть может, я и ошибусь, но тянет на олимпиадную задачу по математике.

~~~~~~~~~~~~~~~~

Впрочем, попробуйте уточнить (у преподавателя): имеется ли в виду квадрат со сторонами, паралельными осям координат. Такая задача намного проще.

 Профиль  
                  
 
 
Сообщение12.12.2006, 14:39 


24/11/06
3
Москва
В принципе это и есть олимпиадная задача...наверно....=)
Это действительно не связано с окружностями (по крайней мере в нашем решении) Хотя вообще бред полный...все еще решаю! Время пока есть...кода решу опубликую :)

 Профиль  
                  
 
 
Сообщение12.12.2006, 21:13 


25/06/06
13
Оренбург
Эту задачу можно решить например так. Переберем все вершины треугольника. Пусть мы выбрали какую-нибудь вершину (если эта вершина содержит тупой угол пропустим ее). Поместим эту вершину в начало координат так, что одна из смежных с этой вершиной сторон будет лежать на оси Y. Обозначим длину стороны лежащей на оси Y за A, длину другой стороны смежной с выбранной вершиной за Б, и длину проекции на ось X третей стороны за C. Тогда исходная задача преобразуется в следующую:
найти минимум по всем X принадлежащим отрезку [0,B-C] от max(X+C,(A*A-X*X)^0,5,(B*B-(X+C)*(X+C))^0,5)

 Профиль  
                  
 
 
Сообщение13.12.2006, 06:30 


24/11/06
3
Москва
Предположим у нас есть прямоугольный, равнобедренный треугольник со сторонами 2, 2, и\sqrt{8}. Пусть мы выбрали вершину, так что, гипотенуза совпадает с осью Y. тогда, A=\sqrt{8}, B=2, C=\sqrt{2}. После прогонки цикла ответ получился 0.585786437626905. А в даном случае ответ должен быть 2, т.к. здесь за дигонал искомова квадрата можно просто взять большую сторону.

 Профиль  
                  
 
 
Сообщение13.12.2006, 11:38 


25/06/06
13
Оренбург
niktof а как у вас получился такой маленький ответ? Ведь мы ищем минимум max(X+C;(A*A-X*X)^0,5;(B*B-(X+C)*(X+C))^0,5) по всем X принадлежащим отрезку [0,B-C], а max(X+C;(A*A-X*X)^0,5;(B*B-(X+C)*(X+C))^0,5) >= X+C >= C. Т.е. в худшем случае у вас может получиться корень из 2.

Добавлено спустя 1 час 21 минуту 49 секунд:

Да, извините niktof, я действительно ошибся. Может быть это вам поможет, хотя и здесь вполне может содержаться ошибка.
Совершенно очевидно, что если мы сможем вписать треугольник в какой-либо квадрат, то этот треугольник мы сможем расположить так, что одна из его вершин совпадет с вершиной квадрата. В принципе это хорошо доказывается по чертежу.
Далее перебираем все вершины треугольника. Если данная вершина имеет тупой угол, то пропускаем ее. Пусть мы сейчас рассматриваем некоторую вершину. Будем предполагать, что в требуемом квадрате треугольник можно расположить так, что рассматриваемая нами его вершина совпадет с вершиной квадрата. Т.к. мы перебираем все вершины и из-за сказанного выше, то хотя бы для одной вершины треугольника это будет верно. Пусть для рассматриваемой вершины это будет верно.
Теперь нарисуем угол квадрата и приложим наш треугольник так, что он будет лежать внутри этого угла и рассматриваемой нами вершина треугольника совпадет с вершиной угла квадрата. Повернем треугольник так, что одна из сторон треугольника смежных с рассматриваемой вершиной будет лежать на вертикальной стороне угла квадрата, и треугольник также будет лежать внутри угла квадрата. Будем вращать треугольник относительно рассматриваемой нами вершины до тех пор, пока другая его сторона смежная с рассматриваемой вершиной не будет лежать на горизонтальной стороне угла, естественно во время вращения треугольник не должен выходить за пределы угла. Для каждого положения треугольника мы будем строить минимальный квадрат, который содержит этот треугольник, и один из углов этого квадрата будет нарисованный нами угол. Из всех построенных квадратов выберем квадрат с минимальной стороной. Этот квадрат совпадет с требуемым квадратом, т.к. мы перебрали все возможные положения треугольника внутри угла квадрата.
Если же в требуемом квадрате треугольник нельзя расположить так, что рассматриваемая нами его вершина совпадет с вершиной квадрата, то тогда в конце наших действий мы получим квадрат, который будем больше требуемого.
Теперь насчет формулы. Обозначим вертикальную сторону угла квадрата за ось Y, горизонтальную за ось X (будем предполагать, что этот угол нарисован “правильно”).
Теперь координаты вершин треугольника имеют вид:
(0,0), (0,A), (sin(d)*B, cos(d)*B), где A – длина стороны треугольника, которая лежит на оси Y, B - длина другой стороны треугольника смежной с рассматриваемой нами вершиной, d – величина угла рассматриваемой нами вершины. Пусть треугольник повернулся на некоторый угол w по часовой стрелке. Тогда координаты его вершин запишутся так: (0,0) , (sin(w)*A,cos(w)*A) ,(sin(w+d)*B,cos(w+d)*B). Можно заметить, что треугольник окончит свое вращение, когда координата по оси Y его третей вершины станет равна нулю, т. е. cos(w+d)*B =0 => w= PI/2-d. В итоге w может изменяться от 0 до PI/2-d. Теперь для любого положения треугольника, сторона минимального квадрата, у которого один из углов совпадает с началом координат, будет вычисляться по следующей формуле –
max( 0 ; 0 ; sin(w)*A ; cos(w)*A ; sin(w+d)*B ; cos(w+d)*B ) = max(sin(w)*A ; cos(w)*A ; sin(w+d)*B ; cos(w+d)*B ).
В итоге получаем: найти минимум по всем w от 0 до PI/2-d от max(sin(w)*A ; cos(w)*A ; sin(w+d)*B ; cos(w+d)*B ) для каждой не “тупоуголной” вершины, и выбрать из этого минимум.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group