ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Plyako                        2:5030/922.20  25 Oct 2002  05:39:32
 To : Max Alekseyev
 Subject : Задача...
 -------------------------------------------------------------------------------- 
 

 
  MA> Есть очевидный трюк: отобразим центрально-симметрично все точки в
  MA> верхнюю полуплоскость и уже потом отсортируем по углу и т.д.
 
 Хм. Hу, не то чтобы это было очевидно... Hо, вроде бы похоже на правду.
 
  MA> Поэтому "в общем случае" перебираем все точки в качестве "центра", для
  MA> каждой за время O(n*log n) находим решение как описано выше. Из этих
  MA> решений выберем лучшее.
 
 Да, правильно. Согласен. Только, зачем же перебирать _все_ комбинации? По
 количеству точек можно всегда определить максимально хорошее деление; как только
 достигли его -- останавливаем вычисления.
 
 Тогда в подавляющем большинстве случаев, время будет ~ n*log n.
 
 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