Посоны, у меня возник вопрос: как строить окружность минимального радиуса, покрывающую заданные точки? Интересуют решения с асимптотикой не более n3. Помнится, где-то обсуждалось, как за O(n) это делать, но там так и не выяснили, верно или нет.
Надеюсь, ни в каком идущем контесте этой задачи нет.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Хаха, бага. Просто почему-то вспомнилась задача с тимуса Кольцо холода, которую я так решал
Это не обязательно будет искомой окружностью. Пример: остроугольный треугольник.
Это далеко не всегда верно. Например для остроугольного треугольника лучше брать описанную окружность.
http://en.wikipedia.org/wiki/Smallest-circle_problem
как-то тут в общих чертах
Во втором и третьем абзацах части "Linear-time solutions" приведен конкретный алгоритм. Доказательство и полное описание можно найти здесь.
Чтобы найти соответствующие статьи/реализации/просто понятные описания, достаточно походить по ссылкам с википедии или просто погуглить по названию.
Вот, например: http://www.tcs.tifr.res.in/workshop/nitrkl_igga/randomized-lecture.pdf
спасибо, вроде разобрался.
Вроде был не так давно топик про задачи, где помогает рэндом-шаффл, эта задача там была.
тут но там вроде так и не выяснили, верно это или нет, и честно говоря, местами не очень понятно
пользуясь случаем, хотел спросить, покатит ли самопальный метод: переберем бинпоиском искомый радиус — R, затем пересечем плоскости, ограниченные дугами радиуса R, предварительно пошафлив точки (это наподобие пересечения плоскостей). верно, что это будет работать и верно ли, что за NlogR?
А вложенный тернарный не покатит?
Покатит. Если определить функцию как f(O) = max(|OAi|), то она будет выпукла вниз, так как функция fi(O) = |OAi| выпукла вниз, а максимум из выпуклых вниз функций — выпуклая вниз функция. А её глобальный минимум будет соответствовать искомому центру оптимальной окружности. Соответственно, алгоритм за O(N log^2 MAX) состоит в нахождении его двум вложенными тернарниками,
http://acm.timus.ru/problem.aspx?space=1&num=1103
И я, пользуясь случаем, хотел бы спросить решение одной похожей задачки. Помогите, пожалуйста, а то как-то совсем не идет. Задача старая, ограничения маленькие, поэтому пусть будет без них.
Есть комната прямоугольной формы размером WxH. Один из ее углов находится в точке (0; 0), противоположный — в (W; H). В этой комнате расположено N колонн, заданных своими координатами. Требуется расположить в этой комнате круглый фонтан максимального радиуса. То есть, грубо говоря, найти окружность максимального радиуса, не покрывающую ни одну из заданных точек и не выходящую за пределы заданного прямоугольника.
По-моему со старого ВКОШПа задача. Делаем бинпоиск по радиусу. Теперь понятно что мы всегда можем упереть окружность-ответ в стену(ы) и(или) точку(и). Накидываем все критические окружности и чекаем. Ограничения небольшие все можно в тупую делать.
По-моему, на intuit есть разбор этой задачи
Эта задача с ВКОШП-a 2000 года, здесь ее разбор.
Работать будет подольше, чем куб, но как вариант, построить выпуклую оболочку, и пробовать описать все треугольники, из возможных взять минимальный радиус.
не понял, зачем выпуклая оболочка?
Да, я понял, не факт, что она описана вокруг треугольника. Тогда выпуклая оболочка и правда незачем)
Интересно, а можно так решать: Пустим градиентный спуск и им будем искать центр окружности. И на каждом шагу считаем максимальное расстояние до центра.
Можно, но уж тогда лучше так. А если еще и золотым сечением это делать, то вообще быстро будет.
Смею заметить, что самую малостью усложненная версия (надо немного преобразований к данным применить) этой задачи была в 90м раунде. Вот кстати ссылка на разбор http://codeforces.com/blog/entry/3229.
Ставь лайк, если решаешь Codeforces Round #514 ;)
Ставь лайк, если тоже не умеешь читать условия заданий.