Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 23.12.2009, 11:57
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Re: я кажется уже доказал для себя, что он должен быть именно равнобедренным
Это неверно. Можно запустить мою программу и увидеть, что треугольники могут быть разными. Или ещё проще, возьмите произвольные 3 точки. Минимальный треугольник будет иметь вершины в этих точках.

Последний раз редактировалось prografix, 23.12.2009 в 12:00.
  #12  
Старый 23.12.2009, 15:50
Новичок

Отправить личное сообщение для saqwer Посмотреть профиль Найти все сообщения от saqwer
 
Регистрация: 22.12.2009
Адрес: Киев
Сообщений: 14

Сообщение от prografix Посмотреть сообщение
Re: я кажется уже доказал для себя, что он должен быть именно равнобедренным
Это неверно. Можно запустить мою программу и увидеть, что треугольники могут быть разными. Или ещё проще, возьмите произвольные 3 точки. Минимальный треугольник будет иметь вершины в этих точках.
да, действительно, Вы правы. Мое утвреждение было поспешным.
Заранее спасибо за статью. Сейчас примусь за изучение.
  #13  
Старый 03.01.2010, 01:04
Новичок

Отправить личное сообщение для saqwer Посмотреть профиль Найти все сообщения от saqwer
 
Регистрация: 22.12.2009
Адрес: Киев
Сообщений: 14

было бы неплохо доказать, что две или хотя бы одна из сторон опуклой
оболочки должна лежать на стороне искомого треугольника. Тогда бы можно было делать эту задачу перебором.
  #14  
Старый 03.01.2010, 16:12
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Одна из сторон выпуклой оболочки точно лежит на стороне треугольника ( ясно интуитивно ). А вот две не обязаны. Пример - квадрат.
  #15  
Старый 03.01.2010, 16:19
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Вот доказательство для одной стороны.
Если ни одна сторона не лежит на стороне треугольника, то треугольник касается трёх точек выпуклой оболочки. В этом случае оптимальный треугольник должен иметь вершины в этих точках. Значит данный треугольник не оптимальный.
  #16  
Старый 04.01.2010, 17:02
Новичок

Отправить личное сообщение для saqwer Посмотреть профиль Найти все сообщения от saqwer
 
Регистрация: 22.12.2009
Адрес: Киев
Сообщений: 14

Сообщение от prografix Посмотреть сообщение
Одна из сторон выпуклой оболочки точно лежит на стороне треугольника ( ясно интуитивно ). А вот две не обязаны. Пример - квадрат.
Позволю себе не согласиться. Для квадрата, как раз таки, наименьшим (по площади) будет прямоугольный треугольник с длинной катета равной удвоенной длине стороны квадрата. И как вы понимаете, катеты будут лежать на сторонах квадрата.
  #17  
Старый 10.01.2010, 08:36
гость

 
Сообщений: n/a

http://ifolder.ru/15850561

(J. O'Rourke, A. Aggarwal, S. Maddila, M. Baldwin. An optimal algorithm for finding minimal enclosing triangles. J. of Algorithms, 7, 1986)

вот тут есть подробное описание алгоритма для данной проблемы с обходом сторон выпуклой оболочки за линейное время с подробным доказательством.
Мало ли... вдруг, кому еще пригодится.
  #18  
Старый 10.01.2010, 12:35
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Сообщение от saqwer Посмотреть сообщение
Позволю себе не согласиться. Для квадрата, как раз таки, наименьшим (по площади) будет прямоугольный треугольник с длинной катета равной удвоенной длине стороны квадрата. И как вы понимаете, катеты будут лежать на сторонах квадрата.
Согласен.

Гость, спасибо за статью. Я её скачал, но прочитаю позже.
  #19  
Старый 11.01.2010, 12:34
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Кстати, мой вариант минимального треугольника вокруг квадрата тоже является оптимальным ( основание длиной 2 высота тоже 2 ).

............../\
........... /....\
......... /_____\
....... / |.......| \
..... / . |...... | . \
... / __ |____|___\
  #20  
Старый 12.01.2010, 04:16
Новичок

Отправить личное сообщение для saqwer Посмотреть профиль Найти все сообщения от saqwer
 
Регистрация: 22.12.2009
Адрес: Киев
Сообщений: 14

Не совсем так.
Если вы имеете ввиду равносторонний треугольник, то длины будут следующими:
х - длина стороны квадрата. Тогда сторона треугольника будет равняться a = (х+2*х*ctg(PI/3)) = х*(1+2/3*sqrt(3)). Высота h = sqrt(3)/2*а = х*(1+sqrt(3)/2).
Отсюда площадь S(прав. треуг.) = 1/2*a*h= 1/2 * х*(1+2/3*sqrt(3)) * х*(1+sqrt(3)/2) =
x^2 * (1+7*sqrt(3)/12) > 2*x^2 = S (прямоуг. треуг.)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение фигуры максимальной площади alienlab Вычислительная геометрия 1 28.04.2009 20:14
Гамильтонов путь минимальной длины гость Графы 5 24.02.2009 01:27
Квадрат гость Задачи 2 17.02.2009 06:48
Покрытие минимальной мощности Marat Galeyev Графы 5 03.01.2008 18:36
максимальны поток минимальной стоимости незарегистрированный Графы 1 28.12.2006 17:37