Hag's Khashba

题意翻译

**【题目描述】** 按逆时针顺序给出一个凸多边形的 n 个顶点，初始第 1,2 个顶点被钉在了墙上 一共有 q 个操作，操作分为两种： 1 f t：解除第 f 个点的钉子，待图形在重力的作用下平衡之后，在第 t 个点处钉上一颗钉子 2 v：询问当第 v 个点的坐标。 **【输入格式】** 第一行两个整数 n (n<=10000)，q (q<=200000)，接下来 n 行，每行两个整数 x,y (|x,y|<=10^8) 表示点的初始坐标。 接下来 q 行表示 q 个操作。 **【输出格式】** 对于每次询问输出两个实数表示坐标。 若您的答案为a，标准答案为b，则当a,b满足  时可通过测试点。 **【样例解释】** 图中红色三角形为初始状态，绿色三角形是绕点(2,0)旋转后的三角形

题目描述

Hag is a very talented person. He has always had an artist inside him but his father forced him to study mechanical engineering. Yesterday he spent all of his time cutting a giant piece of wood trying to make it look like a goose. Anyway, his dad found out that he was doing arts rather than studying mechanics and other boring subjects. He confronted Hag with the fact that he is a spoiled son that does not care about his future, and if he continues to do arts he will cut his 25 Lira monthly allowance. Hag is trying to prove to his dad that the wooden piece is a project for mechanics subject. He also told his dad that the wooden piece is a strictly convex polygon with $ n $ vertices. Hag brought two pins and pinned the polygon with them in the $ 1 $ -st and $ 2 $ -nd vertices to the wall. His dad has $ q $ queries to Hag of two types. - $ 1 $ $ f $ $ t $ : pull a pin from the vertex $ f $ , wait for the wooden polygon to rotate under the gravity force (if it will rotate) and stabilize. And then put the pin in vertex $ t $ . - $ 2 $ $ v $ : answer what are the coordinates of the vertex $ v $ . Please help Hag to answer his father's queries. You can assume that the wood that forms the polygon has uniform density and the polygon has a positive thickness, same in all points. After every query of the 1-st type Hag's dad tries to move the polygon a bit and watches it stabilize again.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 3\leq n \leq 10\,000 $ , $ 1 \leq q \leq 200000 $ ) — the number of vertices in the polygon and the number of queries. The next $ n $ lines describe the wooden polygon, the $ i $ -th line contains two integers $ x_i $ and $ y_i $ ( $ |x_i|, |y_i|\leq 10^8 $ ) — the coordinates of the $ i $ -th vertex of the polygon. It is guaranteed that polygon is strictly convex and the vertices are given in the counter-clockwise order and all vertices are distinct. The next $ q $ lines describe the queries, one per line. Each query starts with its type $ 1 $ or $ 2 $ . Each query of the first type continues with two integers $ f $ and $ t $ ( $ 1 \le f, t \le n $ ) — the vertex the pin is taken from, and the vertex the pin is put to and the polygon finishes rotating. It is guaranteed that the vertex $ f $ contains a pin. Each query of the second type continues with a single integer $ v $ ( $ 1 \le v \le n $ ) — the vertex the coordinates of which Hag should tell his father. It is guaranteed that there is at least one query of the second type.

输出格式

The output should contain the answer to each query of second type — two numbers in a separate line. Your answer is considered correct, if its absolute or relative error does not exceed $ 10^{-4} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is considered correct if $ \frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4} $

输入输出样例

输入样例 #1

3 4
0 0
2 0
2 2
1 1 2
2 1
2 2
2 3

输出样例 #1

3.4142135624 -1.4142135624
2.0000000000 0.0000000000
0.5857864376 -1.4142135624

输入样例 #2

3 2
-1 1
0 0
1 1
1 1 2
2 1

输出样例 #2

1.0000000000 -1.0000000000

说明

In the first test note the initial and the final state of the wooden polygon. Red Triangle is the initial state and the green one is the triangle after rotation around $ (2,0) $ . In the second sample note that the polygon rotates $ 180 $ degrees counter-clockwise or clockwise direction (it does not matter), because Hag's father makes sure that the polygon is stable and his son does not trick him.