Дан набор точек, необходимо найти такую пару, расстояние между которыми максимально. Подскажите быстрый алгоритм. Спасибо.
UPD Решение найдено.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.11.2024 02:15:20 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
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-шку вот отсюда. Та задача с финала скорее на написание тупого куба :).