Задача...

From

Andrew Plyako (2:5030/922.20)

To

Max Alekseyev

Date

2002-10-24T02:42:14Z

Area

RU.ALGORITHMS

Hello Max.
23 Oct 02 14:03, you wrote to Илья Кантор:

[Условия задачи Skiped]

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

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

 MA> Сложность порядка O(n),
Соответсвенно, O(n^2).

Andrew

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