Задача №114867. Перекрытие отрезков
Антон разрабатывает графический движок для 2D игр, который должен покорить рынок. Для того, чтобы объекты отображались корректно, ему нужно уметь выяснять, перекрывают ли объекты друг друга, если игрок смотрит в определённом направлении.
В предварительной версии движка объекты — это непересекающиеся отрезки на плоскости. Отрезок \(a\) перекрывает отрезок \(b\) по направлению вектора \(\vec{v}\), если найдутся такие точки \(A\) на отрезке \(a\) и \(B\) на отрезке \(b\), что вектор \(\overrightarrow{AB}\) сонаправлен с вектором \(\vec{v}\). Другими словами, какая-либо точка отрезка \(a\), двигаясь по направлению вектора \(\vec{v}\), окажется на отрезке \(b\).
Антон сейчас слишком занят поиском инвесторов, поэтому попросил вас реализовать часть движка, которая проверяет перекрытие отрезков.
Первая строка содержит целое число \(n\) — количество проверок на перекрытие отрезков, которые необходимо выполнить (\(1 \le n \le 50\,000\)).
Каждая из следующих \(n\) строк содержит 10 целых чисел: \(ax_1\), \(ay_1\), \(ax_2\), \(ay_2\), \(bx_1\), \(by_1\), \(bx_2\), \(by_2\), \(vx\), \(vy\) — координаты концов первого отрезка, координаты концов второго отрезка и координаты вектора, задающего направление, соответственно. Все координаты не превосходят \(10^6\) по абсолютной величине. Гарантируется, что отрезки невырожденные и не содержат общих точек, а также что вектор \(\vec{v}\) ненулевой.
Для каждой проверки выведите в отдельной строке « Yes », если первый отрезок перекрывает второй отрезок по заданному направлению, иначе выведите « No ».
2 0 2 1 1 2 2 3 1 1 1 0 2 1 1 2 2 3 1 -1 -1
Yes No