/ OIer TK / 题库 /

War

War

测试数据来自 system/1731

描述

C国和J国开战了。

你是C国的指挥官,现在前线传来了一份地形图。

地形图是一个在二维平面上的一个多边形。

设它的顶点是:(x0,y0),(x1,y1)...(xn-1,yn-1),相邻两顶点有边,第n个顶点和第1个顶点有边。

情报人员对地形图进行了加密:
加密之后仍然用n个点表示:(ax0,ay0),(ax1,ay1)...(axn-1,ayn-1)
其中第i个点表示第i条边的中点:
2*axi = xi + x(i+1), 2*ayi = yi + y(i+1), 2*axn-1 = xn-1 + x0, 2*ayn-1 = yn-1 + y0
这样,通过加密后的信息我们就可以得出原图形的顶点坐标了(在大多数情况下)。

现在有三种操作:
1、Q p 查询(xp, yp)的坐标值,如果该多边形不存在,则输出-1,如果有无穷多个坐标,则输出-2
2、D p 将(axp, ayp)删除,其后的点前移一个位置,相当于原多边形减少了一个顶点。

3、I p x y 插入一个中点,坐标为(x, y),插入到p号位置,原来(p~n-1)的点后移一个位置,相当于原多边形增加一个顶点。

你能准确的得出需要查询的顶点坐标吗?

格式

输入格式

第一行,n,q分别表示初始顶点数,操作数
第二行,2n个正整数,表示n个中点的坐标
接下来q行:
首先一个操作符C:
若C为'Q',则接下来一个整数,表示询问的点的编号
若C为'D',则接下来一个整数,表示删除的点的编号
若C为'I',则接下来三个整数,表示插入的位置及坐标
保证读入合法,即设当前有m个点,
则询问的编号在0~m-1之间,删除的编号在0~m-1之间,插入的点的位置在0~m之间

输出格式

对于每一个Q,
如果不存在合法多边形,输出-1
如果坐标有无穷多组解,输出-2
否则输出两个整数,表示坐标(x,y)

样例1

样例输入1

3 10
0 1 1 0 1 1
Q 0
Q 1
Q 2
D 2
D 1
I 0 -1 0
I 0 -1 1
Q 0
Q 1
Q 2

样例输出1

0 2
0 0
2 0
0 2
-2 0
0 0

样例2

样例输入2

4 1
0 1 1 0 2 1 1 2
Q 0

样例输出2

-2

样例3

样例输入3

10 10
1379 39
-525 1609
1035 -109
-1645 -792
-408 -1762
-1213 1044
120 654
-1937 -1691
-346 -1393
1594 -1719
Q 4
I 4 518 -1608
Q 10
Q 3
I 10 -271 -1430
D 4
D 4
D 4
Q 3
D 6

样例输出3

-1
-992 -1078
1698 -998
-2282 -3134

限制

每个测试点1s

提示

多边形是任意的多边形(可以自交,点可以重叠,边可以共线,可以退化成一个点,一条线)
1-3:只有Q操作,n <= 100, q <= 100
4-5:只有Q操作,n <= 10000, q <= 5000
6-8:n <= 1000, q <= 1000
9-10:n <= 50000, q <= 50000
保证读入的坐标范围在[-2000,2000],保证删除操作之后至少有两个点,保证n>=2

温馨提示:暴力可以得很多分

来源

原创(by pty, zzx)
如有雷同,纯属巧合

信息

ID
1670
难度
(无)
分类
其他 | 数学数据结构 | 数据结构 | 平衡树 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者