Кошмар наяву

Автор задачи: Александр Гордеев, разработчик: Мария Жогова

Рассмотрим несколько случаев расположения точек относительно круга:

  1. Обе точки находятся на круге. Тогда при вращении круга прямая между этими двумя точками будет поворачиваться на тот же угол, значит гарантированно существует такой угол поворота, при котором две интересующие нас прямые будут параллельны.

  2. Обе точки находятся вне круга. Тогда при вращении круга вообще не происходит изменения в положении прямых, и достаточно проверить параллельность их исходного положения.

  3. Одна точка (не теряя общности, $$$(x_1, y_1)$$$) находится на круге, а вторая — вне его. В таком случае прямая может поворачиваться в некотором интервале доступных углов. Заметим, что экстремальные значения угол наклона прямой принимает, когда вектор $$$\overrightarrow{C Q_1}$$$ перпендикулярен вектору $$$\overrightarrow{C Q_2}$$$, где $$$C (x, y)$$$ — центр окружности, а $$$Q_1$$$ и $$$Q_2 (x_2, y_2)$$$ — наши точки.

    Обозначим за $$$Q_1^1$$$ и $$$Q_1^2$$$ соответствующие этим двум экстремальным углам положения $$$Q_1$$$ на повернутом круге. Тогда, чтобы проверить, что прямая $$$Q_1 Q_2$$$ может быть параллельной второй прямой, достаточно проверить, что направляющий вектор второй прямой лежит между векторами $$$\overrightarrow{Q_2 Q_1^1}$$$ и $$$\overrightarrow{Q_2 Q_1^2}$$$.

Все описанные выше проверки можно осуществлять с помощью скалярного и веторного произведений векторов.

Альтернативное решение третьего случая — вместо вычисления $$$Q_1^1$$$ и $$$Q_1^2$$$ в явном виде (для чего понадобится поворот вектора на угол), можно повернуть первую прямую относительно $$$Q_2$$$ так, чтобы она стала параллельна второй (то есть на самом деле параллельно сдвинуть вторую до точки $$$Q_2$$$), после чего проверить, что точка $$$Q_1$$$ может оказаться на ее пересечении с кругом. Для этого достаточно проверить, что $$$|C Q_1|$$$ не меньше расстояния от $$$C$$$ до полученной прямой. Все описанные вычисления в таком случае можно совершать в целых числах, не переходя к арифметике чисел с плавающей точкой.