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

链接和思路

OJ链接：传送门

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

1. 拉伸$k$倍：横坐标$x$变为$kx$， 纵坐标$y$ 变为$ky$；
2. 旋转$\theta$ ：将坐标$(x,y)$ 绕坐标原点$(0,0)$ 逆时针旋转$\theta$ 弧度（$0\le \theta <2\pi$）。易知旋转后的横坐标为$x\cos \theta -y\sin \theta$，纵坐标为$x\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$（$1\le i\le j\le n$）后的新坐标。

在考场上，笔者发现此题为区间查询问题，因而首先想到使用树状数组。但是树状数组的建树的时间复杂度虽然为$O(n)$，但是每次查询的时间复杂度为$O(logn)$。而此题不涉及到对区间值的修改，因而无需使用树状数组，只需要记录$k$的前缀和和$\theta$的前缀积即可。前缀和向量和前缀积向量的建立的时间复杂度为$O(n)$，每次区间查询的时间复杂度为$O(1)$。

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

1. 拉伸前缀积向量 k = { k 0 , k 1 , k 2 , ⋯   , k n } \mathbf k = \{k_0,k_1, k_2,\cdots,k_n\} k={k0​,k1​,k2​,⋯,kn​}，其中$k_0=1$，$k_i$为前$i$次操作的总拉伸的倍数，即前缀积；
2. 旋转前缀和向量θ = { θ 0 , θ 1 , θ 2 , ⋯   , θ n } = \{\theta_0,\theta_1, \theta_2,\cdots,\theta_n\} ={θ0​,θ1​,θ2​,⋯,θn​}，其中${\theta }_0=0$，${\theta }_i$为前$i$次操作的总旋转角度，即前缀和。

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

AC代码

#include 

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;
}

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