Очень сложная задача по програмированию(нужны идеи или алгоритмы)

[zorg-kirill]

На трехмерной координатной плоскости заданы координаты сфер (количеством 1-100) и их радиусы, сферы могут пересекаться. Нужно вывести максимальное количество сфер, которые можно пронзить (или коснуться края) лучем, стартующим с точки (0,0,0), и номера этих сфер в любом порядке.
Есть 2 идеи, но их сложно реализовать:
1)перевести сферы в сферическую систему координат, потом спроэцировать ее на плоскость, на ней територию каждой сферы по очереди затемнять к примеру на 1% и потом вывести номера сфер, которые включают в себя самый темный участок;

2)на основе сфер построить конусы, с площадью основы, равной максимальной площади пересечения сферы (тоесть Пи*r*r), а потом найти максимально количество пересекающихся конусов, и вывести ответ.

Если у кого есть идеи реализации или свои методы, прошу помочь)

[Carbon]

Насколько я понимаю, задача несложная

[zorg-kirill]

Сообщение от Carbon

Насколько я понимаю, задача несложная

Ich habe gelernt C++ fur halb Jahr und ich kann nicht mache diese Aufgabe noch.

[Fanyuus]

а если запустить 3 цикла на 3 плоскости (х, у, z), чтобы они проверяли окружности на "соприкасается с линией или нет"

т.е., представить всё в 2д, получается.

[zorg-kirill]

а проверку как сделать?

[Fanyuus]

Проверка... так, если прикинуть, сфера это точки на определённом радиусе. То есть, важно, чтобы хотя бы 1 точка совпадала с 1 точкой из линии.
Вопрос, наверное, даже в том: как определить что 2 точки (допустим, луч пересекает сферу) являются точками одной окружности.
ну, получается, надо ещё впихнуть какую-то проверку, на именно "какие точки принадлежат какой окружности".



возникла ещё идея:
сферы же всё равно каким-то условием задаются, а что если при создании сферы сразу же проверять "луч проходит\соприкасается, или нет", тогда и плюсовать "кол-во сфер" будет проще, в смысле проверки.

[zorg-kirill]

не очень подходит(

[evg_m]

берем сферу единичного радиуса с центром (0,0,0)
луч на данной сфере есть 1 точка
проекция любой сферы (не содержащей внутри себя центр координат(0,0,0) есть некий "круг" если центр внутри то проекция вся сфера
число сфер "проткнутых" лучом = число кругов включающих точку
максимальное число проткнутых сфер = максимальное число наложений кругов (решается перебором комбинаций сфер/кругов и выбором нужной)

К вопросу о выборе системы координат для расчетов

луч на данной сфере есть 1 точка

у точки есть три декартовых координаты(x,y,z)
и две сферических (третья тоже есть но она =const)

берем сферу единичного радиуса

для проекций сфер тоже можно посчитать.

[zorg-kirill]

Как проверять/перебирать комбинации наложения кругов?

[Abstraction]

Например, тупо перебрать все пары. Вычислимое условие пересечения пары кругов выводится с помощью ручки и бумаги.