Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 21.11.2010, 23:45
Новичок

Отправить личное сообщение для Солмир Посмотреть профиль Найти все сообщения от Солмир
 
Регистрация: 21.11.2010
Сообщений: 3

Пересечение шаров. Натолкните на решение
В трехмерном пространстве дано несколько замкнутых шаров. Нужно проверить есть ли точка, которая принадлежит всем шарам.
Вход. В первой строчке дано число шаров N, 1 < N < 20. Затем идут N строчек, каждая из которых содержит 4 натуральных числа X Y Z R соответствующие координатам центров шаров и их радиусам, |X|, |Y|, |Z| < 10000, 1 ≤ R < 10000,
Выход. Строчка со словом NO, если общей точки нет, или YES, если такая точка есть.


Наверно надо измерять расстояние от точки до центра каждого шара и если оно меньше радиуса данного шара то надо чтоб это выполнялось для всех шаров?да?
  #2  
Старый 22.11.2010, 03:16
гость

 
Сообщений: n/a

проверь: 1) центры шаров, 2) для каждой пары пересекающихся шаров - центр окружности, образованной пересечением их сфер, 3) для каждой тройки шаров - точки в которых они пересекаются. Если есть общие точки, то одну из них ты найдешь, проверив все три случая выше. O(n^3) сложность
  #3  
Старый 22.11.2010, 09:35
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
проверь: 1) центры шаров, 2) для каждой пары пересекающихся шаров - центр окружности, образованной пересечением их сфер, 3) для каждой тройки шаров - точки в которых они пересекаются. Если есть общие точки, то одну из них ты найдешь, проверив все три случая выше. O(n^3) сложность
Но ведь тройка шаров может иметь бесконечно много общих точек. Как же проверить их все?
  #4  
Старый 22.11.2010, 09:58
гость

 
Сообщений: n/a

Составь уравнения облатей пересечения всех шаров. Если эта система уравнений не имеет решения, то точек пересечения нет. Иначе - есть.
В задаче не сказано - найти координыты точек. Значит решение системы уравнений не требуется. Достаточно только определить - имеет оно решение или нет при заданных параметрар шаров
  #5  
Старый 22.11.2010, 10:03
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

может, что-то полезное можно вынести из обсуждения двумерного случая:
http://www.rsdn.ru/forum/alg/3319584.all.aspx
  #6  
Старый 22.11.2010, 10:40
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Но ведь тройка шаров может иметь бесконечно много общих точек. Как же проверить их все?
такие случаи игнорируй. это вырожденные случаи, они должны будет покрыться номерами 1) и 2).
  #7  
Старый 22.11.2010, 10:44
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Составь уравнения облатей пересечения всех шаров. Если эта система уравнений не имеет решения, то точек пересечения нет. Иначе - есть. В задаче не сказано - найти координыты точек. Значит решение системы уравнений не требуется. Достаточно только определить - имеет оно решение или нет при заданных параметрар шаров
спасибо, капитан очевидность. тебя просили дать алгоритм, а не пересказать задачу.
  #8  
Старый 22.11.2010, 10:47
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
O(n^3) сложность
пардон, O(n^3) - это вариантов, а каждый из них проверить сложность - O(n^4).
  #9  
Старый 22.11.2010, 12:58
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
такие случаи игнорируй. это вырожденные случаи, они должны будет покрыться номерами 1) и 2).
Это как раз наиболее общий случай
  #10  
Старый 22.11.2010, 13:07
гость

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
пересечение отрезков гость Реализация, исходники, языки 3 18.02.2011 13:17
Пересечение многогранников CtrlShiftB Вычислительная геометрия 16 22.12.2008 19:33
Пересечение отрезков гость Реализация, исходники, языки 1 26.12.2007 00:29
Пересечение отрезков Lomir Задачи 2 22.10.2007 22:50
количество вариантов размещения шаров в корзинах BreakPoint Математические алгоритмы (другое) 10 11.07.2007 12:24