Задача...
- From
- Max Alekseyev (2:5015/60)
- To
- Andrew Plyako
- Date
- 2002-10-24T12:19:20Z
- Area
- RU.ALGORITHMS
████ OS/2 Hi, Andrew !
Replying to a message of Andrew Plyako to Max Alekseyev:
MA>> Полный перебор тут O(n^3).
AP> С этим, согласен.
MA>> Но даже в худшем случае можно управиться за O(n^2 log n).
AP> Может быть и можно, но ты скажи, как :)
MA>> Нет. Достаточно отсортировать точки по возрастанию угла поворота за
MA>> время O(n*log n). Тогда при повороте до очередной точки, с одной
MA>> стороны от прямой число точек уменьшится на единицу,
AP> Ничего подобного. Это будет так, только если ты взял за базу "крайнюю"
AP> точку, т.е. точку на границе выпуклой оболочки. Если же ты вращаешь
AP> прямую вокруг "центральной" точки, то уменьшение может быть и более,
AP> чем на 1. Пример:
AP> DE B
AP> G
AP> F A
AP> H
AP> C
AP> Если вращаем вокруг A, то при прямой AB соотношение 5:1, а при
AP> следующей прямой (вращаем по часовой стрелке) AC, соотношение уже 3:3
Есть очевидный трюк: отобразим центрально-симметрично все точки в верхнюю полуплоскость и уже потом отсортируем по углу и т.д.
На деле же ничего отображать не надо, достаточно сортировать не по значению угла, а по значению тангенса угла (как известно, тангенсы углов у центрально-симметричных равны).
MA>> Когда про расположение точек ничего не известно, можно перебрать
MA>> всевозможные "центры". Это решит задачу за время O(n^2*log n).
AP> Вот этой фразы я, не понял. Как ты собираешься переходить от частного
AP> случая (никакие 3 точки не лежат на одной прямой) к частному?
То, что написано выше, в любом случае находит лучшее решение для выбранного центра. Просто в случае, когда возможны "три точки на одной прямой", это решение может оказаться глобально неоптимальным.
Поэтому "в общем случае" перебираем все точки в качестве "центра", для каждой за время O(n*log n) находим решение как описано выше. Из этих решений выберем лучшее.
Regards, ° °
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)