Как оказалось, Railgun обожает задачи на геометрию. Его наставник в этом деле, fractal, дал ему множество из $$$N$$$ точек на плоскости, некоторые из них можно сделать анимешными. Особенность анимешной точки (условно $$$H$$$) в том, что имея произвольную точку $$$P$$$, можно за одну операцию превратить ее в точку $$$P'$$$, повернув относительно $$$H$$$ на какой-либо угол. Иными словами, если описать окружность $$$\omega$$$ вокруг точки $$$H$$$ радиуса $$$dist(H, P)$$$, то должно выполняться $$$P' \in \omega$$$.
Также fractal дал ему $$$Q$$$ независимых запросов: имея произвольную точку $$$A(x, y)$$$, сказать, возможно ли из нее перейти в точку $$$B(-x, -y)$$$, вращая ее вокруг анимешных точек. Изначально у Railgun нет анимешных точек. А так как делать их долго, он попросил вас сказать наименьшее количество анимешных точек, которые ему пригодятся (если, конечно, запрос fractal осуществим). А так же сказать сколько существует способов выбрать их. Так как это число может быть большим, он попросил вывести его по модулю $$$10^9 + 7$$$.
Количество операций минимизировать не нужно.
Первая строка входных данных содержит два целых числа $$$N$$$, $$$Q$$$ $$$(1 \le N, Q \le 10^5)$$$.
Следующие $$$N$$$ строк описывают точки множества и содержат два целых числа $$$x$$$, $$$y$$$ $$$(-10^9 \le x, y \le 10^9)$$$. Гарантируется что все точки множества различные.
Следующие $$$Q$$$ строк описывают запросы и содержат два целых числа $$$Ax$$$, $$$Ay$$$ $$$(-10^9 \le Ax, Ay \le 10^9)$$$.
Для каждого запроса на отдельной строке выведите $$$-1$$$ $$$-1$$$, если запрос fractal неосуществим. В ином случае, выведите два целых числа — минимальное количество точек, которые нужно сделать анимешными и количество способов их выбрать по модулю $$$10^9 + 7$$$.
Между запросами анимешные точки не сохраняются.
5 31 12 23 -34 40 5-1 13 0-1 -1
1 3 1 1 1 1
| Almaty Code Cup 2024 |
|---|
| Закончено |
