Дан набор точек, необходимо найти такую пару, расстояние между которыми максимально. Подскажите быстрый алгоритм. Спасибо.
UPD Решение найдено.
Дан набор точек, необходимо найти такую пару, расстояние между которыми максимально. Подскажите быстрый алгоритм. Спасибо.
UPD Решение найдено.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 4 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 135 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
http://cgm.cs.mcgill.ca/~orm/diam.html
Выпуклая оболочка, а потом 2 указателя, не?
да, я знаю. Но нельзя ли поподробнее?
Строим выпуклую оболочку за O(N log N). Получаем выпуклый многоугольник. Теперь используем два указатель: текущее ребро многоугольника и самая удаленная от него вершина. Двигаем первый указатель в порядке обхода многоугольника(каждый раз на 1). Второй указатель двигаем в порядке обхода, пока расстояние растет. Ответ — максимум из расстояний между концами ребра и самой удаленной от этого ребра вершиной(пересчет на каждом шаге). Итого O(N log N) + O(N) = O(N log N). Upd: расстояние между ребром и вершиной — расстояние между прямой, проходящей через 2 соседние вершины, и третьей вершиной.
Спасибо. Понял
upd. Бред написал, понял ошибку.
Контрпример против предложенного в upd: многоугольник из 6 вершин с координатами {(0, 0), (2, 2), (2, 4), (0, 6), (-2, 4), (-2, 2)}. Если начать из точки номер 6, то получим точки номер 1 и 3, а надо — 1 и 4. Upd: опечатался: вместо (2, 4) надо (2, 5), вместо (-2, 4) надо (-2, 5).
Кажется можно переделать алгоритм http://e-maxx.ru/algo/nearest_points, в котором в стадии объединения будем идти не от ближайших точек, пока расстояние по y меньше R, а наоборот от дальних, пока расстояние по y больше R. То есть тот же O(N*log(N))
Хм. Интересно, почему минусуют пост. Я не прав? Если так, можете обосновать? А то мне действительно интересно и кажется, что так должно работать.
Я полагаю, что количество таких точек уже не будет О(1).
Почему? Я ж говорю, пусть мы отсортили все точки по Y. В задаче о минимуме теперь побежим по каждой и для i-ой точки мы должны были бы рассмотреть все точки, ниже неё и у которых Y отстаёт не дальше чем на текущее минимальное R. Но ввиду того, что у нас идёт постоянная релаксация R, то получается сложность O(1) в среднем. Это было для минимума. А для максимума поступим наоборот: для i-ой точки нужно рассмотреть все точки, у которых Y больше Yi на R, ну и рассматривать будем не от Y а наоборот от самой нижней и двигаясь к i, релаксируя R, таким образом тоже получим большое сокращение и O(1) сложность в среднем.
Во-первых, фраза "для i-ой точки нужно рассмотреть все точки, у которых Y больше Yi на R" — достаточно наивная, ведь очевидно, что для того чтобы расстояние между точками было максимально не обязательно максимизировать одно из расстояний по х или у. Во-вторых, я, конечно, не великий теоретик, но кол-во точек при поиске минимума не больше 7 в силу того, что их можно в худшем случае поместить в прямоугольник 2RxR, а не "ввиду того, что у нас идёт постоянная релаксация R, то получается сложность O(1) в среднем".
Да, понятно, что по x мы тоже отсеиваем. Я тоже не теоретик, но полагаю можно доказать, что в этом случае тоже будет что-то около 8ми в прямоугольнике.
UPD. И да, я конечно не говорю, что "ввиду того, что у нас идёт постоянная релаксация R" обосновывает факт сложности O(1), я так выразился для простоты, дабы не доказывать сей факт, но чтобы меня поняли.
Нет, ты не понимаешь) В поиске минимума все просто благодаря тому, что если по одной из координат расстояние>R то дальше смысла нету искать. А при поиске максимального расстояния такие рассуждение неправильные, ибо если расстояние по Х меньше текущего ответа, то это некоем образом не означает что реальное расстояние между точками меньше ответа.
Если уж совсем не веришь в мои слова, то проверь все брутфорсом:)
Теперь понял, согласен.
Я кстати на spoj когда сдавал задачу о минимальном расстоянии вначале забыл ограничивать по X и решение прошло, причём кажется даже с лучшим временем, чем когда сделал по алгоритму. Не знаю, может у них там тесты слабые.
У меня на сподже прошла сортировка по Х-координате и потом для каждой точки смотреть только 20-30 соседних. Заламывать такие решения довольно сложно, как правило.
А можно ссылочку на задачу? Интересно стало решить.
Не совсем то, но rotating calipers можно здесь попробовать.
По-моему совсем не то...
Один из алгоритмов нахождения этой пары точек — convex hull + rotating calipers (сверху его описал kraskevich). Ну вот тут и можно попробовать написать эти rotating calipers.
По-моему, лучше в качестве примера на convex hull + rotating calipers давать D-шку вот отсюда. Та задача с финала скорее на написание тупого куба :).