Блог пользователя Gerald

Автор Gerald, 14 лет назад, По-русски
Задача предложена Раховым Артемом (RAD.). 
Решение:
Посмотрим на ГМТ точек куда может приземлиться ДравДэ, есть несколько случаев: 
  1. ГМТ - угол, в том случае, если проекции их на плоскость Oxy есть вектора линейно независимые. Получить этот угол достаточно просто. Вершина его будет очевидно в точке старта ДравДэ, один из образующих лучей будет сонаправлен с проекцией вектора скорости самолета, другой просто вычисляется 
    Az  + Vz * tv + Uz *  tu = 0
    Ax  + Vx * tv + Ux*  tu = Bx
    Ay  + Vy * tv + Uy *  tu = By
    где A стартовая точка, а B та точка куда ДравДэ приземлится. Подставив в качестве tv 
    например 1 можно легко вычислить t2 из первого уравнения и далее найти точку B. Это и будет точка на втором луче.
  2. ГМТ - луч или прямая, в том случае если проекции векторов скоростей линейно зависимы, луч когда ветер дует не слишком сильно =). 
Понятно, что ответ существует только в том случае, если есть пересечения многоугольника и ГМТ приземления. Так же легко понять, что минимальные времена полета получаются в критических точках, то есть в точках пересечения многоугольника и сторон угла (и с лучом), а также в  вершинах многоугольника. Найдем времена t1, t2 во всех таких точках и выберем минимальные (в смысле минимальности описанной в условии). Искать эти времена можно их естественных соображений, тогда будут возникать случаи ---> ифы ---> БАГИ. Намного удобнее выписать все соотношения в виде линейных уравнений и решить их. (там тоже возникают неприятные случаи, но в этом случае их намного меньше).
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Если не секрет, есть ли в 42ом тесте что-то особенное, кроме номера?)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
в этом тесте область куда может попасть рембо целиком захватывает весь многоугольник