|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
11.12.2012, 20:53 | #1 |
Пользователь
Регистрация: 11.11.2012
Сообщений: 32
|
Очень сложная задача по програмированию(нужны идеи или алгоритмы)
На трехмерной координатной плоскости заданы координаты сфер (количеством 1-100) и их радиусы, сферы могут пересекаться. Нужно вывести максимальное количество сфер, которые можно пронзить (или коснуться края) лучем, стартующим с точки (0,0,0), и номера этих сфер в любом порядке.
Есть 2 идеи, но их сложно реализовать: 1)перевести сферы в сферическую систему координат, потом спроэцировать ее на плоскость, на ней територию каждой сферы по очереди затемнять к примеру на 1% и потом вывести номера сфер, которые включают в себя самый темный участок; 2)на основе сфер построить конусы, с площадью основы, равной максимальной площади пересечения сферы (тоесть Пи*r*r), а потом найти максимально количество пересекающихся конусов, и вывести ответ. Если у кого есть идеи реализации или свои методы, прошу помочь) |
11.12.2012, 22:06 | #2 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
Насколько я понимаю, задача несложная
|
12.12.2012, 20:36 | #3 |
Пользователь
Регистрация: 11.11.2012
Сообщений: 32
|
Ich habe gelernt C++ fur halb Jahr und ich kann nicht mache diese Aufgabe noch.
Последний раз редактировалось zorg-kirill; 13.12.2012 в 00:09. |
12.12.2012, 20:41 | #4 |
Форумчанин
Регистрация: 07.05.2011
Сообщений: 169
|
а если запустить 3 цикла на 3 плоскости (х, у, z), чтобы они проверяли окружности на "соприкасается с линией или нет"
т.е., представить всё в 2д, получается. |
12.12.2012, 21:14 | #5 |
Пользователь
Регистрация: 11.11.2012
Сообщений: 32
|
а проверку как сделать?
|
12.12.2012, 21:51 | #6 |
Форумчанин
Регистрация: 07.05.2011
Сообщений: 169
|
Проверка... так, если прикинуть, сфера это точки на определённом радиусе. То есть, важно, чтобы хотя бы 1 точка совпадала с 1 точкой из линии.
Вопрос, наверное, даже в том: как определить что 2 точки (допустим, луч пересекает сферу) являются точками одной окружности. ну, получается, надо ещё впихнуть какую-то проверку, на именно "какие точки принадлежат какой окружности". возникла ещё идея: сферы же всё равно каким-то условием задаются, а что если при создании сферы сразу же проверять "луч проходит\соприкасается, или нет", тогда и плюсовать "кол-во сфер" будет проще, в смысле проверки. |
12.12.2012, 22:06 | #7 |
Пользователь
Регистрация: 11.11.2012
Сообщений: 32
|
не очень подходит(
|
13.12.2012, 12:38 | #8 | ||
Старожил
Регистрация: 20.04.2008
Сообщений: 5,528
|
берем сферу единичного радиуса с центром (0,0,0)
луч на данной сфере есть 1 точка проекция любой сферы (не содержащей внутри себя центр координат(0,0,0) есть некий "круг" если центр внутри то проекция вся сфера число сфер "проткнутых" лучом = число кругов включающих точку максимальное число проткнутых сфер = максимальное число наложений кругов (решается перебором комбинаций сфер/кругов и выбором нужной) К вопросу о выборе системы координат для расчетов Цитата:
и две сферических (третья тоже есть но она =const) Цитата:
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 13.12.2012 в 12:53. |
||
13.12.2012, 13:52 | #9 |
Пользователь
Регистрация: 11.11.2012
Сообщений: 32
|
Как проверять/перебирать комбинации наложения кругов?
|
13.12.2012, 14:05 | #10 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Например, тупо перебрать все пары. Вычислимое условие пересечения пары кругов выводится с помощью ручки и бумаги.
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
очень сложная задача! | extrayellow | Microsoft Office Excel | 1 | 19.11.2012 22:34 |
Очень сложная задача! | XYLIGAN72 | Помощь студентам | 8 | 30.01.2012 14:09 |
Очень сложная задача на Pascal ABC! | d00ker | Помощь студентам | 8 | 11.02.2009 22:02 |
Интересная задача. Нужны идеи ее решения | KnDmPetr | Паскаль, Turbo Pascal, PascalABC.NET | 11 | 05.03.2008 18:43 |