125 lines
3.1 KiB
Markdown
125 lines
3.1 KiB
Markdown
# P16055 [CSPro 31] 坐标变换（其二） 题解
|
|
|
|
这篇题解主要针对不懂得矩阵乘法的人。主要思想：
|
|
|
|
视每次操作为：
|
|
|
|
$$
|
|
newx = x * k1 - y * k2\\
|
|
newy = x * k2 + y * k1\\
|
|
x = newx, y = newy
|
|
$$
|
|
|
|
其中：
|
|
|
|
- 操作为 $1$ 时，$k1 = k, k2 = 0$。
|
|
- 操作为 $2$ 时，$k1 = \cos(\theta), k2 = \sin(\theta)$。
|
|
|
|
## 80 pts 暴力
|
|
|
|
注意到 $80%$ 的测试点满足 $n, m \le 1000$，此时最大执行次数为 $1000 \times 1000 = 10^6$，可以获得此部分分。
|
|
|
|
::::info[[80 pts 代码](https://www.luogu.com.cn/record/303033043)]
|
|
|
|
```cpp
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
int n, m;
|
|
vector<pair<int, double>> o;
|
|
double k1[100005], k2[100005];
|
|
int main() {
|
|
scanf("%d%d", &n, &m);
|
|
o.push_back({0, 0});
|
|
for (int i = 1; i <= n; ++i) {
|
|
int op;
|
|
double k;
|
|
scanf("%d%lf", &op, &k);
|
|
o.push_back({op, k});
|
|
if (op == 2) {
|
|
k1[i] = cos(k);
|
|
k2[i] = sin(k);
|
|
} else {
|
|
k1[i] = k;
|
|
k2[i] = 0;
|
|
}
|
|
}
|
|
for (int i = 1; i <= m; ++i) {
|
|
int l, r, x, y;
|
|
scanf("%d%d%d%d", &l, &r, &x, &y);
|
|
double nx = x, ny = y;
|
|
for (int j = l; j <= r; ++j) {
|
|
if (o[j].first == 1)
|
|
nx *= o[j].second, ny *= o[j].second;
|
|
else {
|
|
double tmpx = nx * k1[j] - ny * k2[j],
|
|
tmpy = nx * k2[j] + ny * k1[j];
|
|
nx = tmpx, ny = tmpy;
|
|
}
|
|
}
|
|
printf("%f %f\n", nx, ny);
|
|
}
|
|
return 0;
|
|
}
|
|
```
|
|
|
|
::::
|
|
|
|
## 100 pts st 表
|
|
|
|
注意到连续一段的操作可以由各部分操作叠加，可使用 st 表解决。
|
|
|
|
::::info[[100pts 代码](https://www.luogu.com.cn/record/303042049)]
|
|
|
|
```cpp
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
int n, m;
|
|
vector<pair<int, double>> o;
|
|
double st1[200005][21], st2[200005][21];
|
|
int main() {
|
|
scanf("%d%d", &n, &m);
|
|
o.push_back({0, 0});
|
|
for (int i = 1; i <= n; ++i) {
|
|
int op;
|
|
double k;
|
|
scanf("%d%lf", &op, &k);
|
|
o.push_back({op, k});
|
|
if (op == 1) {
|
|
st1[i][0] = k;
|
|
st2[i][0] = 0;
|
|
|
|
} else {
|
|
st1[i][0] = cos(k);
|
|
st2[i][0] = sin(k);
|
|
}
|
|
}
|
|
for (int i = 1; i <= 20; i++) {
|
|
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
|
|
double tmp11 = st1[j][i - 1], tmp12 = st2[j][i - 1];
|
|
double tmp21 = st1[j + (1 << (i - 1))][i - 1],
|
|
tmp22 = st2[j + (1 << (i - 1))][i - 1];
|
|
st1[j][i] = tmp11 * tmp21 - tmp12 * tmp22;
|
|
st2[j][i] = tmp11 * tmp22 + tmp12 * tmp21;
|
|
}
|
|
}
|
|
while (m--) {
|
|
int l, r, x, y;
|
|
scanf("%d%d%d%d", &l, &r, &x, &y);
|
|
double nx = x, ny = y;
|
|
r++;
|
|
for (int i = 20; i >= 0; i--) {
|
|
if (l + (1 << i) <= r) {
|
|
double tmpx = st1[l][i] * nx - st2[l][i] * ny,
|
|
tmpy = st2[l][i] * nx + st1[l][i] * ny;
|
|
nx = tmpx, ny = tmpy;
|
|
l += 1 << i;
|
|
}
|
|
}
|
|
printf("%f %f\n", nx, ny);
|
|
}
|
|
return 0;
|
|
}
|
|
```
|
|
|
|
::::
|