ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Plyako                        2:5030/922.20  24 Oct 2002  08:51:46
 To : Max Alekseyev
 Subject : Задача...
 -------------------------------------------------------------------------------- 
 

 
  AP>> 1) Это как раз-таки, частный случай, а не общий.
  MA> Это с какой стороны посмотреть.
 
 Общий случай, это случай, когда ты не прибавляешь к условиям задачи никаких доп.
 условий. Логично?
  AP>> 2) В общем случае -- мы ничего не знаем о положении точек -- твой
  AP>> алгоритм не приемлим; точнее, его работоспособная модификация
  AP>> сведется к полному перебору.
  MA> Хм. Hет.
 
 Хм. Да. :)
 
  MA> Полный перебор тут O(n^3).
 
 С этим, согласен.
 
  MA> Hо даже в худшем случае можно управиться за O(n^2 log n).
 
 Может быть и можно, но ты скажи, как :)
 
  MA> Hет. Достаточно отсортировать точки по возрастанию угла поворота за
  MA> время O(n*log n). Тогда при повороте до очередной точки, с одной
  MA> стороны от прямой число точек уменьшится на единицу,
 
 Hичего подобного. Это будет так, только если ты взял за базу "крайнюю" точку,
 т.е. точку на границе выпуклой оболочки. Если же ты вращаешь прямую вокруг
 "центральной" точки, то уменьшение может быть и более, чем на 1. Пример:
    DE     B
 G
 F    A
 H
           C
 
 Если вращаем вокруг A, то при прямой AB соотношение 5:1, а при следующей прямой 
 (вращаем по часовой стрелке) AC, соотношение уже 3:3
 
 Соответсвенно, поиск элемента из выпуклой оболочки это еще ~ n операций.
 
  MA> Когда про расположение точек ничего не известно, можно перебрать
  MA> всевозможные "центры". Это решит задачу за время O(n^2*log n).
 
 Вот этой фразы я, не понял. Как ты собираешься переходить от частного случая
 (никакие 3 точки не лежат на одной прямой) к частному?
 
 Andrew
 
 ---
  * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Задача...   Artem Rogetdinov   22 Oct 2002 10:19:00   Re: Задача...   Viktor Karev   23 Oct 2002 16:35:06   Re: Задача...   €«мп Љ ­в®а   23 Oct 2002 21:48:54   Задача...   Max Alekseyev   23 Oct 2002 14:03:02   Задача...   Andrew Plyako   24 Oct 2002 02:42:14   Задача...   Max Alekseyev   23 Oct 2002 18:54:12   Задача...   Andrew Plyako   24 Oct 2002 08:51:46   Задача...   Max Alekseyev   24 Oct 2002 12:19:20   Задача...   Andrew Plyako   25 Oct 2002 05:39:32