|
Шары
(Время: 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)
| |