| Codeforces Round 478 (Div. 2) |
|---|
| Закончено |
Хэг — очень талантливый человек. В нём всегда была жилка художника, но его отец заставил его заниматься машиностроением. Вчера Хэг потратил весь свой день, вырезая гуся из гигантского куска дерева. К сожалению, его отец узнал, что Хэг занимается искусством вместо штудирования механики и прочих скучных предметов. Он обвинил Хэга в том, что он не заботится о своём будущем и пригрозил, что если он продолжит занимать искусством, он перестанет давать ему 25 лир в месяц.
Хэг пытается доказать своему отцу, что этот кусок дерева на самом деле был проектом для курса механики. Он также сообщил ему, что этот кусок является строго выпуклым многоугольником с $$$n$$$ вершинами.
Хэг принёс две кнопки и прикрепил деревянный многоугольник к стене за $$$1$$$-ю и $$$2$$$-ю вершины. У отца есть $$$q$$$ запросов для Хэга двух типов.
- $$$1$$$ $$$f$$$ $$$t$$$. Этот запрос означает, что Хэг вынимает кнопку из вершины $$$f$$$, ждёт когда многоугольник повернётся (если он повернётся) и остановится, после чего он прикрепляет вершину $$$t$$$ к стене кнопкой.
- $$$2$$$ $$$v$$$. Этот запрос означает, что Хэг должен ответить, каковы координаты вершины $$$v$$$.
Помогите Хэгу ответить на запросы его отца.
Вы можете считать, что дерево, из которого сделан многоугольник, обладает одинаковой положительной плотностью во всех точках. Также известно, что после каждого запроса первого типа отец Хэга немного шевелит многоугольник и смотрит на повторное установление его равновесия.
В первой строке содержится два целых числа $$$n$$$ и $$$q$$$ ($$$3\leq n \leq 10\,000$$$, $$$1 \leq q \leq 200000$$$) — число вершин в многоугольнике и число запросов.
Следующие $$$n$$$ строк содержат описание деревянного многоугольника, $$$i$$$-я из которых содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$|x_i|, |y_i|\leq 10^8$$$) — координаты $$$i$$$-й вершины многоугольника. Гарантируется, что многоугольник строго выпуклый, вершины заданы в порядке против часовой стрелки и различны.
В следующих $$$q$$$ строках содержатся запросы, по одному на строку. Каждый запрос начинается с его типа — $$$1$$$ или $$$2$$$. Каждый запрос первого типа продолжается двумя целыми числами $$$f$$$ и $$$t$$$ ($$$1 \le f, t \le n$$$) — вершина, из которой убирается кнопка, и вершина, в которую вставляется кнопка после того, как вращение заканчивается. Гарантируется, что в вершине $$$f$$$ есть кнопка. Каждый запрос второго типа продолжается одним целым числом $$$v$$$ ($$$1 \le v \le n$$$) — номером вершины, координаты которой Хэг должен сообщить своему отцу.
Гарантируется, что существует хотя бы один запрос второго типа.
На каждый запрос второго типа выведите ответ — два числа в отдельной строке. Ваш ответ будет засчитан, если его относительная или абсолютная ошибка не превышает $$$10^{-4}$$$.
Формально, пусть ваш ответ — $$$a$$$, а ответ жюри — $$$b$$$. Ваш ответ считается верным, если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.
3 4
0 0
2 0
2 2
1 1 2
2 1
2 2
2 3
3.4142135624 -1.4142135624
2.0000000000 0.0000000000
0.5857864376 -1.4142135624
3 2
-1 1
0 0
1 1
1 1 2
2 1
1.0000000000 -1.0000000000
Ниже приведены изначальное и конечное состояния деревянного многоугольника в первом примере.
Красный треугольник обозначает начальное состояние, а зелёный — треугольник после поворота вокруг $$$(2,0)$$$.
Во втором примере заметьте, что многоугольник поворачивается на $$$180$$$ градусов против или по часовой стрелки (не важно, куда), поскольку отец Хэга удостоверяется, что многоугольник устойчив и его сын не обманывает его.
