ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      23 Oct 2002  18:54:12
 To : Andrew Plyako
 Subject : Задача...
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Andrew Plyako to Max Alekseyev:
 
  MA>> Для простоты рассмотрим случай общего положения точек (никакие три не
  MA>> лежат на одной прямой).
  AP> 1) Это как раз-таки, частный случай, а не общий.
 
 Это с какой стороны посмотреть. Hедаром указанное положение называется "общим".
 
  AP> 2) В общем случае -- мы ничего не знаем о положении точек -- твой
  AP> алгоритм не приемлим; точнее, его работоспособная модификация
  AP> сведется к полному перебору.
 
 Хм. Hет. Полный перебор тут O(n^3). Hо даже в худшем случае можно управиться за 
 O(n^2 log n). См. ниже.
 
  MA>> пока не добьешься требуемого условия.
  AP> Проверка "требуемого условия" потребует еще, как минимум [n/2]-1
  AP> операцию.
 
 Hет. Достаточно отсортировать точки по возрастанию угла поворота за время
 O(n*log n). Тогда при повороте до очередной точки, с одной стороны от прямой
 число точек уменьшится на единицу, а с другой соответственно увеличится.
 Соответственно, достаточно посчитать баланс в начале вращения, и сразу вычислить
 порядковый номер точки до которой нужно совершить поворот.
 
  MA>> Сложность порядка O(n),
  AP> Соответсвенно, O(n^2).
 
 Истина посередине: O(n*log n) (для общего положения).
 
 Когда про расположение точек ничего не известно, можно перебрать всевозможные
 "центры". Это решит задачу за время O(n^2*log n).
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.8
  * Origin:  (2:5015/60)
 
 

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

Тема:    Автор:    Дата:    Задача...   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