Задача...

From

Andrew Plyako (2:5030/922.20)

To

Max Alekseyev

Date

2002-10-24T08:51:46Z

Area

RU.ALGORITHMS

Hello Max.
23 Oct 02 18:54, you wrote to me:

 AP>> 1) Это как раз-таки, частный случай, а не общий.
 MA> Это с какой стороны посмотреть.
Общий случай, это случай, когда ты не прибавляешь к условиям задачи никаких доп. условий. Логично?


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

 MA> Полный перебор тут O(n^3).
С этим, согласен.

 MA> Но даже в худшем случае можно управиться за O(n^2 log n).
Может быть и можно, но ты скажи, как :)

 MA> Нет. Достаточно отсортировать точки по возрастанию угла поворота за
 MA> время O(n*log n). Тогда при повороте до очередной точки, с одной
 MA> стороны от прямой число точек уменьшится на единицу,
Ничего подобного. Это будет так, только если ты взял за базу "крайнюю" точку, т.е. точку на границе выпуклой оболочки. Если же ты вращаешь прямую вокруг "центральной" точки, то уменьшение может быть и более, чем на 1. Пример:
   DE     B
G
F    A
H
          C

Если вращаем вокруг A, то при прямой AB соотношение 5:1, а при следующей прямой (вращаем по часовой стрелке) AC, соотношение уже 3:3

Соответсвенно, поиск элемента из выпуклой оболочки это еще ~ n операций.

 MA> Когда про расположение точек ничего не известно, можно перебрать
 MA> всевозможные "центры". Это решит задачу за время O(n^2*log n).
Вот этой фразы я, не понял. Как ты собираешься переходить от частного случая (никакие 3 точки не лежат на одной прямой) к частному?

Andrew

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