Моя идея достаточно простая. Будем бинарным поиском искать наименьший достаточный радиус, каждый раз проверяя - можно ли в этом случае покрыть все точки двумя кругами.
Для проверки мы будем перебирать все разумные возможные места установки круга. Достаточно двух случаев. 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