Дано N объектов на плоскости (x, y) , каждый из которых представлен как (sx, sy, vx, vy) , где каждый объект начинается в точке (sx, sy) и перемещается в направлении вектора (vx, vy) . Таким образом, каждую секунду объект будет двигаться vx единиц в направлении x и vy единиц в направлении y. Если вы начнете с начала координат (0, 0) и будете двигаться со скоростью S единиц / секунду, какое минимальное количество времени (секунд) потребуется для достижения всех объектов. (достижение объекта считается занятым той же (x, y) координатой, что и объект в данный момент времени).
Пример:
- N = 2, S = 4
- Объект 1: (8, 0, -2, 0)
- Объект 2: (-10, 0, -2, 0)
- Ответ = 8
- Объяснение: Второй объект встречается в (- 20, 0) через 5 секунд. Тогда объект один находится в (- 2, 0) , и вы изменяете направление, чтобы встретиться в (- 8, 0) еще через 3 секунды.
Я могу решить эту проблему в O (N!) Раз, однако меня интересует поиск более быстрого алгоритма.
** Предполагается, что все данные случаи решаемы / не существует невозможных случаев, которые будут дано
** Ограничения для задачи: (ограничения по времени 4 с и ограничение памяти 256 МБ)
- 1≤N≤15
- 0≤ | скс |, | sy | ≤100
- 0≤ | vx |, | vy | ≤10
- 1≤S≤100
Гарантируется, что все данные случаи разрешимы