CCF CSP题解：坐标变换（其二）（202309-2）

本文主要是介绍CCF CSP题解：坐标变换（其二）（202309-2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接和思路

OJ链接：传送门

对于平面直角坐标系上的坐标 $(x, y)$ ，定义如下两种操作：

拉伸 $k$ 倍：横坐标 $x$ 变为 $k x$ ，纵坐标 $y$ 变为 $k y$ ；
旋转 $\theta$ ：将坐标 $(x, y)$ 绕坐标原点 $(0, 0)$ 逆时针旋转 $\theta$ 弧度（ $\le \theta < 2 \pi$ ）。易知旋转后的横坐标为 $\cos \theta - y \sin \theta$ ，纵坐标为 $\sin \theta + y\cos \theta$ 。

本题要求将平面坐标 $(x, y)$ ，经过 $n$ 个操作 $(t_1, t_2, \cdots, t_n)$ 后，对于给定的操作序列，计算 $m$ 个如下查询：

i j x y：坐标 $(x, y)$ 经过操作 $t_i, \cdots, t_j$ （ $\le i \le j \le n$ ）后的新坐标。

在考场上，笔者发现此题为区间查询问题，因而首先想到使用树状数组。但是树状数组的建树和查询成本都太高，而此题不涉及到对区间值的修改，因而只需要记录 $k$ 的前缀和和 $\theta$ 的前缀积即可。前缀和向量的建立只需要线性代价，而每次区间查询只需要常数级别的代价。

具体而言，由于拉伸和旋转2种行为相互独立，我们只需分别求出经过 $n$ 个操作 $(t_1, t_2, \cdots, t_n)$ 后，总共旋转的角度和拉伸的倍数。我们仅需维护2个向量：

拉伸前缀积向量 $\mathbf k = \{k_0,k_1, k_2,\cdots,k_n\}$ ，其中 $k_0=1$ ， $k_i$ 为前 $i$ 次操作的总拉伸的倍数，即前缀积；
旋转前缀和向量 $\mathbf{\theta} = \{\theta_0,\theta_1, \theta_2,\cdots,\theta_n\}$ ，其中 $\theta_0=0$ ， $\theta_i$ 为前 $i$ 次操作的总旋转角度，即前缀和。

被查询坐标 $(x, y)$ 经过 $t_i, \cdots, t_j$ （ $\le i \le j \le n$ ）后，拉伸倍数为 $k_j / k_{i-1}$ ，角度为 $\theta_j-\theta_{i-1}$ 。

AC代码

#include <bits/stdc++.h>using namespace std;int n, m;vector<double> xita(100005);
vector<double> k(100005, 1);int main() {cin >> n >> m;for (int i = 1; i <= n; ++i) {int type;double value;cin >> type >> value;if (type == 1) {k[i] = k[i - 1] * value;xita[i] = xita[i - 1];} else {k[i] = k[i - 1];xita[i] = xita[i - 1] + value;}}for (int i = 0; i < m; ++i) {int l, r;double x, y;cin >> l >> r >> x >> y;double sum_xita = xita[r] - xita[l - 1];double pro_k = k[r] / k[l - 1];cout << fixed << setprecision(3) << (x * cos(sum_xita) - y * sin(sum_xita)) * pro_k << " "<< (x * sin(sum_xita) + y * cos(sum_xita)) * pro_k << endl;}return 0;
}