eolymp
bolt
Try our new interface for solving problems
Məsələlər

Бильярд

Бильярд

Пусть \textbf{G }- выпуклый многоугольник, \textbf{p }- точка, лежащая строго вне многоугольника. Из точки \textbf{p }к \textbf{G }проведено две касательных. Давайте возьмем "правую" точку (относительно \textbf{p}) и предположим, что \textbf{q }- точка касания, а \textbf{r }- точка, симметричная \textbf{p}, где \textbf{q }- центр симметрии. Пусть \textbf{r }= \textbf{T}(\textbf{p}) и назовем \textbf{T }\textit{биллиардным преобразованием}. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/2c/2c13416e5c2e45c051648c0f1387a6a65f76974b.jpg} \includegraphics{https://static.e-olymp.com/content/a5/a5cf45fecc599d199cc90508960b832cd6cdd640.jpg} \includegraphics{https://static.e-olymp.com/content/49/49270e28ebc371c9e6e548fe5edf6353526f0ecb.jpg} Касательная \textbf{pq }из точки \textbf{p }к выпуклому многоугольнику \textbf{G}, где \textbf{q }- точка касания, называется правой, если для любой точки \textbf{uG }вращение против часовой стрелки от вектора к вектору совершается по углу в интервале \[\textbf{0}, ). Приведем пример, который поможет понять сущность преобразования \textbf{T}. Пусть \textbf{G }- треугольник с вершинами (\textbf{0}, \textbf{0}), (\textbf{2}, \textbf{0}), (\textbf{1}, \textbf{1}), точка \textbf{p }имеет координаты (\textbf{-1}, \textbf{-1}). Тогда "правая" касательная пройдет через вершину (\textbf{2}, \textbf{0}), поэтому \textbf{T}(\textbf{p}) = (\textbf{5}, \textbf{1}). Аналогично \textbf{T}((\textbf{3, 0})) = (\textbf{-1, 2)}, \textbf{T}((\textbf{3, 2})) = (\textbf{-1, 0}), \textbf{T}((\textbf{3, 4})) = (\textbf{-3, -4}). В некоторых случаях "правая" касательная может касаться многоугольника не в вершине, а в стороне. Если этот случай имеет место, то \textbf{T}(\textbf{p}) неопределено. Например, для многоугольника \textbf{G }значения \textbf{T}((\textbf{3}, \textbf{3})), \textbf{T}((\textbf{-1},\textbf{ 0})), \textbf{T}((\textbf{4},\textbf{ -2})) неопределены. Рассмотрим последовательность \textbf{S}(\textbf{p}) = (\textbf{p, T}(\textbf{p}), \textbf{T}(\textbf{T}(\textbf{p})), ...). В зависимости от поведения последовательности множество всех точек \textbf{p }вне многоугольника разобьется на классы: \begin{enumerate} \item Последовательность \textbf{S}(\textbf{p}) конечна (то есть \textbf{T}(\textbf{v})\textbf{ }неопределено для последнего значения \textbf{v}). \item Последовательность \textbf{S}(\textbf{p}) бесконечна и периодична, возможно с некоторым предпериодом. \item Последовательность \textbf{S}(\textbf{p}) бесконечна и не периодична. \end{enumerate} В задаче "бильярдным столом", или фигурой \textbf{G}, является параллелограмм \textbf{OABC}, где \textbf{O} = (\textbf{0}, \textbf{0)}. Вам заданы координаты некоторого "стола" и точка строго вне его. Выясните тип последовательности. Если последовательность периодическая (типа \textbf{2}), то найдите ее период. \InputFile Первая строка содержит количество тестов \textbf{T }(\textbf{1 }≤ \textbf{T }≤ \textbf{3·10^5}). Каждая из следующих \textbf{T }строк содержит шесть целых чисел \textbf{x_A}, \textbf{y_A}, \textbf{x_C}, \textbf{y_C}, \textbf{x_p}, \textbf{y_p}, не превышающих по модулю \textbf{10^9}: координаты точек \textbf{A}, \textbf{C }и\textbf{ p}. Гарантируется, что параллелограмм \textbf{OABC }невырожденный, а точка \textbf{p }лежит вне многоугольника. \OutputFile Для каждого теста вывести в отдельной строке одно число: \begin{itemize} \item \textbf{-1}, если последовательность конечна, \item Длину периода, если последовательность периодична, \item \textbf{-3}, если последовательность бесконечна и не периодична. \end{itemize}
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
2
0 2 2 0 1 -1
1 0 0 1 -1 1
Çıxış verilənləri #1
4
-1
Mənbə 2013 Петрозаводск, MIPT contest, Август 25, Задача D