推荐题目：洛谷 P5843 [SCOI2012] Blinker 的噩梦
推荐题目：洛谷P5843 [SCOI2012] Blinker 的噩梦
题目描述
一天 Blinker 醒来，发现自己成为了一个二维世界的点，而且被标记上了一个奇怪的值。
这个世界是由N NN个边界互不相交（且不相切）的图形组成，这里图形仅包括圆和凸多边形。每个图形还有一个权值。每次 Blinker 走进或走出某个图形时（相切时经过不算），Blinker 的标记值就会被异或上那个值。
现在，我们记录了 Blinker 在这个世界的M MM天的信息。每天可能发生两种事情，一种是某个图形的权值更改为某个值；另一种是 Blinker 从某个点走到另一个点。
我们假设 Blinker 首次出发前的标记值为0 00，我们希望知道他每次到达目的地后的标记值。
输入格式
输入的第一行包含2 22个数，N NN和M MM，分别表示这个世界的图形数和记录的天数。
接下来有N NN行，每行表示一个图形。
如果一行以字符C开头，表示这个图形是一个圆，后面紧跟着三个实数x xx,y yy,r rr和一个整数v vv，分别表示圆的x xx坐标，y yy坐标和圆的半径以及该图形对应的值。
如果一行以字符P开头，表示这个图形是凸多边形，后面紧跟着一个整数L LL，表示凸多边形的点数，然后后面有L LL对实数x 0 x_0x0,y 0 y_0y0,x 1 x_1x1,y 1 y_1y1⋯ \cdots⋯，表示L LL个点的坐标，这一行最后一个数是一个整数v vv，表示这个图形对应的值，保证凸多边形上的点按照顺时针给出。
接下来有M MM行，每行表示一天的记录信息。
如果一行以字符Q开头，表示这一天 Blinker 出行了，接下来有x 0 , y 0 , x 1 , y 1 x_0,y_0,x_1,y_1x0,y0,x1,y1四个实数，分别表示出发点的坐标和目的地的坐标。
如果一行以字符C开头，表示这一天某个图形的值改变了，接下来有两个i ii和v vv，表示输入中第i ii个出现的图形的值变成v vv。
输出格式
对于 Blinker 的每个出行输出他到达目的地后的标记值，很显然这个值与 Blinker 的路径无关。
输入输出样例 #1
输入 #1
2 4 C 0 0 2 1 P 4 -1 -1 -1 1 1 1 1 -1 2 Q -2 -2 2 2 Q -1.5 0 0.0 0.0 C 1 1005 Q -1.5 0 0.0 0.0输出 #1
0 2 0说明/提示
样例解释
样例的世界形如上图：
第一天 Binker 的初始标记值为0 00，可能从A AA沿直线走到B BB，或者他绕过圆走到B BB，他的标记值最终都保持不变为0 00（假设沿直线从A AA走到B BB，共穿过4 44次边界，Binker 的标记值变化过程为1 , 3 , 1 , 0 1,3,1,01,3,1,0）;
第二天 Binker 的初始标记值为0 00，他通过某种不经过图形边界的方法到达了C CC点（即 Binker 瞬间移动或闪烁），然后从C CC沿某种路径走到D DD，这时他的标记值变为2 22；
第三天圆的权值变为1005 10051005；
第四天 Binker 的初始标记值为2 22，他再次回到C CC，并再次从C CC走到D DD，这时他的标记值又变为0 00。
数据范围
- 对于30 % 30\%30%的数据，1 ≤ M ≤ 10.00 1 \le M \le 10.001≤M≤10.00，凸多边形的点数加上圆的个数小于等于1000 10001000；
- 对于100 % 100\%100%的数据，1 ≤ N ≤ 10 5 1 \le N \le 10^51≤N≤105，1 ≤ M ≤ 10 5 1 \le M \le 10^51≤M≤105，单个凸多边形的点数小于等于34 3434。图形互不相交，且 Binker 的出发点和目的地不在图形的边界。