Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » problem from UVa
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
На днях проходил контест, где встретилась эта задача Towers for mobile telephony.
Хотелось бы знать ваши мнения, как правильно разбить множество точек на два подмножества(для 1-ой окружности и для 2-ой).
А потом, как я полагаю:
1)находим центры масс для 1-го множества и для 2-го, которыми должны оказаться центры окружностей.
2)затем наибольшее расстояние от центра окружности до точки соответствующего подмножества.
Моя идея достаточно простая. Будем бинарным поиском искать наименьший достаточный радиус, каждый раз проверяя - можно ли в этом случае покрыть все точки двумя кругами.
Для проверки мы будем перебирать все разумные возможные места установки круга. Достаточно двух случаев. 1) Проведенный через две точки(в две стороны) 2) с центром в любой точке(тоже надо обязательно рассмотреть, т.к. 1 круг может покрывать всего 1 точку в оптимальном построении).
Т.о. получается n*n+n возможных расположений кругов. Найдем соответственно все их центры и за линейное время для каждого определим какие точки он накрывает и представим это в виде массива масок, поскольку у нас максимум 40 точек и это влезает в 64-bit. Теперь мы за O(n^3) получили все возможные маски, и их около n^2.
Но у нас два круга, значит мы перебираем все возможные пары масок за O(n^4) и проверяем дают ли они в итоге полное покрытие - if ( (mask(i] | mask[j]) == (1L<<n)-1 )
Если такая пара нашлась - значит покрытие данным радиусом возможно.
Общая сложность этого алгоритма выходит O(log(m)*n^4), но константа тут получается очень маленькая.
Accepted JAVA 0.608 2009-09-22 12:54:44
На Codejam Round 2 дали почти эту же задачу...
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » problem from UVa