Помогоите решить олимпиадную задачу - [2] :: Прикладное программирование

max0z
Конечно есть.
Сводится она, в общем, к следующему (напишу для плоскости).
1. Для множества S окружностей (s1, s2, ..., sN), заданных уравнениями:
(x1-a1)^2 + (y1-b1)^2 = с1^2
....
(xN-aN)^2 + (yN-bN)^2 = cN^2
определить, существует ли прямая ax + by + z = 0, которая пересекает каждую сферу из заданного множества S. + И найти один из вариантов a, b и z (само собой их может быть много).
Если данная задача решается, то исходная решается перебором. Для оптимизации можно вместо перебора строить дерево решений - задачу можно свести к следующей. Есть множество S1 окружностей для которых такая прямая существует. Определить существует ли она для множества S2 полученного из S1 добавлением еще одной окружности.

На предыдущей странице FuzzyLogic описал как это сделать. Т.е. основная идея (FuzzyLogic - сорри, я немного с другой стороны подойду) - записываем уравнение прямой в виде y = ax + b. Собственно нас интересует коэффициент a - он определяет угол наклона. Для двух окружностей получим интервал - [a1, a2] - он описывает угол наклона всех прямых проходящих одновременно через обе окружности. Если такая прямая существует для множества окружностей S, то пересечение множества соответствующих интервалов углов наклона прямых непустое. При добавлении новой окружности - просто осуществляем эту проверку.

Дальше можно перейти от плоскости к 3-х мерному пространству, - будет достаточно решать данную задачу для проекций шаров на плоскости X Y Z (одновременно). Т.е. при добавлении новой сферы - рассчитываем ее проекции на каждую из плоскостей и в каждой из них проверяем описанное выше условие. Если во всех 3 ответ утвердителен, то такая прямая существует.

Это будет работать - вычисления сами по себе несложные, но их достаточно много. Интересует, есть ли более эффективный алгоритм решения данной задачи.

Надеюсь что нигде не ошибся

Модерирует : ShIvADeSt
Версия для печати • Подписаться • Добавить в закладки
Страницы: 1 2 3