Задача...

From

Andrew Plyako (2:5030/922.20)

To

Max Alekseyev

Date

2002-10-25T05:39:32Z

Area

RU.ALGORITHMS

Hello Max.
24 Oct 02 12:19, you wrote to me:

 MA> Есть очевидный трюк: отобразим центрально-симметрично все точки в
 MA> верхнюю полуплоскость и уже потом отсортируем по углу и т.д.
Хм. Ну, не то чтобы это было очевидно... Но, вроде бы похоже на правду.

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

Тогда в подавляющем большинстве случаев, время будет ~ n*log n.

Andrew

---
 * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)