ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      24 Oct 2002  12:19:20
 To : Andrew Plyako
 Subject : Задача...
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Andrew Plyako to Max Alekseyev:
 
  MA>> Полный перебор тут O(n^3).
  AP> С этим, согласен.
 
  MA>> Hо даже в худшем случае можно управиться за O(n^2 log n).
  AP> Может быть и можно, но ты скажи, как :)
 
  MA>> Hет. Достаточно отсортировать точки по возрастанию угла поворота за
  MA>> время O(n*log n). Тогда при повороте до очередной точки, с одной
  MA>> стороны от прямой число точек уменьшится на единицу,
  AP> Hичего подобного. Это будет так, только если ты взял за базу "крайнюю"
  AP> точку, т.е. точку на границе выпуклой оболочки. Если же ты вращаешь
  AP> прямую вокруг "центральной" точки, то уменьшение может быть и более,
  AP> чем на 1. Пример:
  AP>    DE     B
  AP> G
  AP> F    A
  AP> H
  AP>           C
 
  AP> Если вращаем вокруг A, то при прямой AB соотношение 5:1, а при
  AP> следующей прямой (вращаем по часовой стрелке) AC, соотношение уже 3:3
 
 Есть очевидный трюк: отобразим центрально-симметрично все точки в верхнюю
 полуплоскость и уже потом отсортируем по углу и т.д. 
 Hа деле же ничего отображать не надо, достаточно сортировать не по значению
 угла, а по значению тангенса угла (как известно, тангенсы углов у
 центрально-симметричных равны).
 
  MA>> Когда про расположение точек ничего не известно, можно перебрать
  MA>> всевозможные "центры". Это решит задачу за время O(n^2*log n).
 
  AP> Вот этой фразы я, не понял. Как ты собираешься переходить от частного
  AP> случая (никакие 3 точки не лежат на одной прямой) к частному?
 
 То, что написано выше, в любом случае находит лучшее решение для выбранного
 центра. Просто в случае, когда возможны "три точки на одной прямой", это решение
 может оказаться глобально неоптимальным.
 
 Поэтому "в общем случае" перебираем все точки в качестве "центра", для каждой за
 время O(n*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