Задача...

From

Max Alekseyev (2:5015/60)

To

Andrew Plyako

Date

2002-10-23T18:54:12Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Andrew !

Replying to a message of Andrew Plyako to Max Alekseyev:

 MA>> Для простоты рассмотрим случай общего положения точек (никакие три не
 MA>> лежат на одной прямой).
 AP> 1) Это как раз-таки, частный случай, а не общий.

Это с какой стороны посмотреть. Недаром указанное положение называется "общим".

 AP> 2) В общем случае -- мы ничего не знаем о положении точек -- твой
 AP> алгоритм не приемлим; точнее, его работоспособная модификация
 AP> сведется к полному перебору.

Хм. Нет. Полный перебор тут O(n^3). Но даже в худшем случае можно управиться за O(n^2 log n). См. ниже.

 MA>> пока не добьешься требуемого условия.
 AP> Проверка "требуемого условия" потребует еще, как минимум [n/2]-1
 AP> операцию.

Нет. Достаточно отсортировать точки по возрастанию угла поворота за время 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)