[Pascal] Нужна помощь в разработке алгоритма

[artems67]

Здраствуйте,

Хочу сразу предупредить, что задача уровня вузовской олимпиады.

Условие:

Корабли повстанцев предприняли попытку прорваться мимо Звезды смерти. Звезда смерти захватывает корабль, если он находится в сфере ее влияния (сфера радиусом R) не менее, чем T секунд. Заданы начальные координаты x, y, z каждого корабля относительно Звезды смерти и проектции векторов скорости vx, vy, vz. Считать, что корабли движутся строго по прямой. Определить, сколько кораблей сможет уйти в прорыв.


Входные данные:
В первой строке указано: количество кораблей — целое число N (1≤N≤100), сфера влияния — действительное число R > 0 (а.е.), время — действительное число T > 0 (сек).
В последующих N строках для каждого корабля указаны шесть действительных чисел: начальные координаты x, y, z (а.е.) и проекции векторов скорости vx, vy, vz (а.е./сек).

Выходные данные:
Количество прорвавшихся кораблей.

Пример:

Входные данные
3 3 6
-3 -3 -3 1 1 1
3 3 3 1 1 1
1000 1000 1000 -1 -1 -1

Выходные данные
1

Я понял условие выхода корабля из зоны так, что величина перемещения тела должна быть больше, чем радиус сфера. здесь пошаговый алгоритм нахождения пермещения. Но для использования этого алгоритма мне не хватает значения x,y,z вместо этого мне даны проекции векторов скорости vx, vy, vz. Дальше я наткнулся на этот сайт. И тут говорится что Ux=dx/dt, к примеру, но я не могу понять, как это мне поможет найти x . Даже попытался привязать сюда кинематику. Пытался комбинировать формулы, но в выходных данных у меня не получается 1.

Если есть у кого желание поломать голову и помочь с разработкой алгоритма, милости прошу. 1 голова хорошо, а 2 лучше.

[Аватар]

Условие какое-то не полное. Что происходит с кораблем, попадающем в сферу влияния? Если падает скорость - то по какому закону? Если захватывает это не движется T секунд, а потом вперед, то рано или поздно выйдет из этой сферы

[artems67]

Сообщение от Аватар

Условие какое-то не полное. Что происходит с кораблем, попадающем в сферу влияния? Если падает скорость - то по какому закону? Если захватывает это не движется T секунд, а потом вперед, то рано или поздно выйдет из этой сферы

Из условия все что было написал. Если попал в сферу влияния, то должен успеть за T секунд её покинуть, если не успевает то считается "сбитым" и не подсчитывается при выводе кол-ва прорвавшихся кораблей. Я так понял.

[GreenWizard]

Гуглим "пересечение прямой и окружности", находим, например, это, подправляем для 3д, находим точки входа-выхода каждого корабля в сферу, считаем время пребывания и там уже погиб\прорвался

[artems67]

Мозги уже плавятся. Решил пойти через пересечения сферы по двум точкам. С геометрией у меня туго, так что выложу свои догадки на общее обозрение.

1) Составляем параметрическое уравнение прямой:

(1)

2) Составляем уравнение сферы:



3) Подставляем (1) в (2) , после некоторых преобразований получится квадратное уравнение с 1-м неизвестным t .

4)По школьной методике нахожу квадратное уравнение через дискриминант. В ответе получу t1, t2

5) Подставлю t1 в (1) получу точку входа/выхода в сферу ? Аналогично для t2 найду вторую точку пересечения прямой со сферой.

Окей, имею точку входа и выхода для прямой. Пока не совсем разобрался как мне рассчитать за сколько T от точки входа до точки выхода в сферу корабль доберется.

И вообще немного сумбурно написал, так как повторяюсь, что мозг плавится.

[GreenWizard]

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

Окей, имею точку входа и выхода для прямой. Пока не совсем разобрался как мне рассчитать за сколько T от точки входа до точки выхода в сферу корабль доберется.

И вообще немного сумбурно написал, так как повторяюсь, что мозг плавится.

Выше ссылка на расчёт вход-выход.
Вычитаем выход из входа (получаем вектор), а далее делим его на вектор скорости... либо можно сразу их длины делить т. к. оно параллельное (мы же находим точки эти по пути движения)