Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Шары

(Время: 2 сек. Память: 16 Мб Сложность: 37%)

Заметим, что два шара пересекаются, если расстояние между центами меньше суммы радиусов. Формально, если (x1,y1,z1) и (x2,y2,z2) – центры шаров, а r1 и r2 – их радиусы то факт пересечения данных шаров эквивалентен выполнению следующего неравенства:

При возведении обеих частей в квадрат, мы можем избавиться от корня:

Все шары будем хранить в массиве структур с полями x,y,z,r и ok, где (x,y,z) – координата центра шара, r – радиус, а ok – логическое значение, отражающее факт пересечения данного шара с каким-либо другим шаром. Для определения искомого шара будем моделировать процесс добавления шаров по одному и на каждом шаге при размещении нового шара проверять его пересечение со всеми предыдущими. При этом в случае каждого пересечения будем помечать каждый шар как попавший под пересечение. Как только в результате добавления окажется, что все шары пересекаются, следует вывести номер последнего добавленного шара и завершить работу программы. В конце программы следует вывести символ «0».

Факт пересечения всех шаров можно определить с помощью линейного алгоритма, перебирающего все шары и подсчитывающего число тех, поле ok которых обращено в true. Это не изменит порядок сложности исходного алгоритма O(N2), но замедлит его работу. Здесь можно поступить более эффективно: при каждом определении факта пересечения шара следует некоторую переменную k увеличивать на единицу. Делать это следует только тогда, когда текущий шар ранее не пересекался с другими. Если до работы алгоритма переменную k обнулить, то в каждый момент ее значение будет соответствовать числу пересекающихся шаров, что позволит легко определить время завершения процесса.

Алгоритмическая реализация данного решения:

a[0..5000]{
  float x,y,z,r //центр шара и радиус
  bool ok       //факт пересечения с другими шарами
}

read(a[0], n)

k=0
for i=1..n{
  for j=0..n-1
    if(dist(a[i], a[j]) < a[i].r+a[j].r){
      if(not a[i].ok) k++
      if(not a[j].ok) k++
      a[i].ok = a[j].ok = true  
    }
  if(k>i){write(i); halt}
}

write(0)

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru