「计蒜客16620」银河战舰 - 线段树+仿射变换

题目大意

题目描述

    瑞奥和玛德利德是非常好的朋友。瑞奥平时的爱好是吹牛，玛德利德的爱好是戳穿瑞奥吹的牛。
    这天瑞奥和玛德利德来到了宇宙空间站，瑞奥向玛德利德炫耀这个空间站里所有的银河战舰都是自己的。整个空间站可以看成一个无限大的二维平面，而每个战舰都可以看做一个点，在空间站中一共分布着N艘银河战舰。
    玛德利德：“你说这些都是你的，那你让他们动一动啊”
    瑞奥：“诶你看，那艘动了！”
    玛德利德：“操作指令由我来发，一共有$5$种动的方法……”
    瑞奥：“我觉得这样有失公正……”

输入格式

    第一行一个正整数$N$，表示战舰的数量。
    接下来$N$行，每行两个实数，代表第$i$个战舰的$x,y$坐标。
    然后一个正整数$M$，代表调度的次数。
    接下来$M$行操作，每个操作都是如下类型的一种：
    $M\,l\,r\,p\,q$：把编号在$[l,r]$区间内的战舰$x$坐标加上$p$,$y$坐标加上$q$。
    $X\,l\,r$：把编号在$[l,r]$区间内的战舰沿$x$轴翻转。
    $Y\,l\,r$：把编号在$[l,r]$区间内的战舰沿$y$轴翻转。
    $O\,l\,r$：把编号在$[l,r]$区间内的战舰沿直线$y=x$翻转。
    $R\,l\,r\,a$：把编号在$[l,r]$区间内的战舰绕原点逆时针旋转$a$°。

输出格式

    输出包括$N$行，代表着$N$艘战舰经过$M$次调度之后的坐标(保留两位小数)

数据范围

---

题目分析

发现所有的操作均可以使用齐次坐标用矩阵相乘的形式表示。

齐次坐标是指将坐标系用矩阵表示。
点可以使用$\begin{pmatrix}x & y & 1\end{pmatrix}$表示。（采用行向量方便编程实现）

比如旋转可以采用乘上矩阵
$\begin{bmatrix}
\cos(alpha) & \sin(alpha) & 0 \\
-\sin(alpha) & \cos(alpha) & 0 \\
0 & 0 & 1
\end{bmatrix}$

对于区间操作，我们可以用线段树维护。
线段树的叶子结点表示具体序列，线段树的非叶子结点起到寻址与下传标记的作用。

对于区间乘上矩阵，我们可以在线段树的对应结点处乘上该矩阵，然后在访问其儿子时下传该矩阵即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

struct Matrix {
	int n,m;
	double a[5][5];
	Matrix() {}
	Matrix(int n,int m) {
		init(n,m);
	}
	Matrix(int n,int m,char E) { //单位矩阵
		init(n,m);
		for(int i=1; i<=n; i++)a[i][i]=1;
	}
	void init(int n,int m) {
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
	}
	inline double* operator [] (const int x) {
		return a[x];
	}
	Matrix operator * (Matrix b) {
		Matrix c(n,b.m);
		for(int i=1; i<=n; i++)
			for(int j=1; j<=b.m; j++)
				for(int k=1; k<=m; k++)
					c[i][j]+=a[i][k]*b[k][j];
		return c;
	}
	void operator *= (Matrix b) {
		*this=*this*b;
	}
};

const int maxn=100005;

struct Tree {
	Matrix a;
	int left,right;
	Tree(int l=0,int r=0):a(Matrix(3,3,'E')),left(l),right(r) {}
};

struct Segment_Tree {
	Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
	void build(int index,int Left,int Right,const Matrix* a) {
		tree[index]=Tree(Left,Right);
		if(Left==Right) {
			tree[index].a=a[Left];
			return;
		}
		int mid=(Left+Right)>>1;
		build(ls,Left,mid,a);
		build(rs,mid+1,Right,a);
	}
	void push_down(int index) {
		tree[ls].a*=tree[index].a;
		tree[rs].a*=tree[index].a;
		tree[index].a=Matrix(3,3,'E');
	}
	void modify(int index,int Left,int Right,const Matrix& v) {
		if(Left>tree[index].right||Right<tree[index].left)return;
		if(Left<=tree[index].left&&Right>=tree[index].right) {
			tree[index].a*=v;
			return;
		}
		push_down(index);
		modify(ls,Left,Right,v);
		modify(rs,Left,Right,v);
	}
	void dfs(int index) {
		if(tree[index].left==tree[index].right) {
			printf("%0.2lf %0.2lf\n",tree[index].a[1][1],tree[index].a[1][2]);
			return;
		}
		push_down(index);
		dfs(ls);
		dfs(rs);
	}
} st;

Matrix a[maxn];
int n,m;
const double pi=acos(-1);

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++) {
		a[i]=Matrix(1,3);
		scanf("%lf%lf",&a[i][1][1],&a[i][1][2]);
		a[i][1][3]=1;
	}
	st.build(1,1,n,a);
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		char opt=' ';
		while(!isalpha(opt))opt=getchar();
		int l=Get_Int(),r=Get_Int();
		if(opt=='M') {
			double ax,ay;
			scanf("%lf%lf",&ax,&ay);
			Matrix add(3,3,'E');
			add[3][1]=ax;
			add[3][2]=ay;
			st.modify(1,l,r,add);
		}
		if(opt=='X') {
			Matrix add(3,3,'E');
			add[2][2]=-1;
			st.modify(1,l,r,add);
		}
		if(opt=='Y') {
			Matrix add(3,3,'E');
			add[1][1]=-1;
			st.modify(1,l,r,add);
		}
		if(opt=='O') {
			Matrix add(3,3);
			add[1][2]=add[2][1]=add[3][3]=1;
			st.modify(1,l,r,add);
		}
		if(opt=='R') {
			double alpha;
			scanf("%lf",&alpha);
			alpha*=pi/180;
			Matrix add(3,3);
			add[1][1]=cos(alpha),add[1][2]=sin(alpha);
			add[2][1]=-sin(alpha),add[2][2]=cos(alpha);
			add[3][3]=1;
			st.modify(1,l,r,add);
		}
	}
	st.dfs(1);
	return 0;
}