隐藏
「计蒜客16620」银河战舰 - 线段树+仿射变换 | Bill Yang's Blog
0%

「计蒜客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}$

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

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#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;
}
姥爷们赏瓶冰阔落吧~