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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 01.07.2010, 23:54
Новичок

Отправить личное сообщение для Evil Genius Посмотреть профиль Найти все сообщения от Evil Genius
 
Регистрация: 01.07.2010
Сообщений: 1

Треугольник min площади
Дано N точек на плоскости. необходимо найти из них 3 точки, которые образуют треугольник минимальной площади среди всех возможных N!/(3!*(N-3)!) вариантов. Кроме очевидного перебора всех троек за O(N^3) ничего не приходит на ум пока. Может кто может придумать алгоритм меньшей сложности..Например за O(N^2*logN) или там O(N^2) или поделится ссылками....заранее спасибо!
  #2  
Старый 02.07.2010, 00:50
Новичок

Отправить личное сообщение для =[miKroZ]= Посмотреть профиль Найти все сообщения от =[miKroZ]=
 
Регистрация: 07.01.2008
Адрес: Санкт-Петербург
Сообщений: 25

А случайно триангуляция Делоне не прокатит?
__________________
Irreparabilium felix oblivio rerrum.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вписанный треугольник. гость Задачи 0 11.12.2009 07:56
Определить, лежит ли треугольник ... alex_8 Вычислительная геометрия 1 17.10.2009 20:51
Треугольник Паскаля ronzo Реализация, исходники, языки 4 07.12.2008 14:16
Самый быстрый способ закрасить треугольник Riasoft Обработка изображений, звук, графика 1 01.08.2007 02:40
Прямоугольный треугольник ГеоMetric Вычислительная геометрия 2 09.07.2007 14:58