CCF CSP 第30次（2023.09）（2_坐标变换（其二）_C++）

时间限制： 2.0 秒
空间限制： 512 MiB

题目背景：

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

1. 拉伸 k 倍：横坐标 x 变为 kx，纵坐标 y 变为 ky；
2. 旋转 θ：将坐标 (x,y) 绕坐标原点 (0,0) 逆时针 旋转 θ 弧度（0≤θ<2π）。易知旋转后的横坐标为xcos⁡θ−ysin⁡θ，纵坐标为 xsin⁡θ+ycos⁡θ。设定好了包含 n 个操作的序列 (t1,t2,⋯,tn) 后，小 P 又定义了如下查询：

• i j x y：坐标 (x,y) 经过操作 ti,⋯,tj（1≤i≤j≤n）后的新坐标。
  对于给定的操作序列，试计算 m 个查询的结果。

题目描述：

输入格式：

从标准输入读入数据。
输入共 n+m+1 行。
输入的第一行包含空格分隔的两个正整数 n 和 m，分别表示操作和查询个数。
接下来 n 行依次输入 n 个操作，每行包含空格分隔的一个整数（操作类型）和一个实数（k 或 θ），形如 1 k（表示拉伸 k 倍）或 2 θ（表示旋转 θ）。
接下来 m 行依次输入 m 个查询，每行包含空格分隔的四个整数 i、j、x 和 y，含义如前文所述。

输出格式：

输出到标准输出中。
输出共 m 行，每行包含空格分隔的两个实数，表示对应查询的结果。

样例输入：

10 5
2 0.59
2 4.956
1 0.997
1 1.364
1 1.242
1 0.82
2 2.824
1 0.716
2 0.178
2 4.094
1 6 -953188 -946637
1 9 969538 848081
4 7 -114758 522223
1 9 -535079 601597
8 8 159430 -511187

样例输出：

-1858706.758 -83259.993
-1261428.46 201113.678
-75099.123 -738950.159
-119179.897 -789457.532
114151.88 -366009.892

样例解释：

第五个查询仅对输入坐标使用了操作八：拉伸 0.716 倍。
横坐标：159430×0.716=114151.88
纵坐标：−511187×0.716=−366009.892
由于具体计算方式不同，程序输出结果可能与真实值有微小差异，样例输出仅保留了三位小数。

子任务：

80% 的测试数据满足：n,m ≤ 1000；
全部的测试数据满足：

• n,m≤10⁵；
• 输入的坐标均为整数且绝对值不超过 10⁶；
• 单个拉伸操作的系数 k∈[0.5,2]；
• 任意操作区间 ti,⋯,tj（1 ≤ i ≤ j ≤ n）内拉伸系数 k 的乘积在 [0.001,1000] 范围内。

评分方式

如果你输出的浮点数与参考结果相比，满足绝对误差不大于 0.1，则该测试点满分，否则不得分。

提示：

• C/C++：建议使用 double 类型存储浮点数，并使用 scanf(“%lf”, &x); 进行输入，printf(“%f”, x);
  输出，也可以使用 cin 和 cout 输入输出浮点数；#include <math.h> 后可使用三角函数 cos() 和 sin()。
• Python：直接使用 print(x) 即可输出浮点数 x；from math import cos, sin 后可使用相应三角函数。
• Java：建议使用 double 类型存储浮点数，可以使用 System.out.print(x); 进行输出；可使用
  Math.cos() 和 Math.sin() 调用三角函数。

解题思路：

思路一（哈希集合）：

1、解题步骤拆分：
① 输入：首先输入两个整数 n 和 m，n 表示操作的数量，m 表示查询的次数。接下来输入 n 个操作及其参数，操作包括拉伸和旋转。

② 操作存储：

• op[i] 存储每个操作的类型（1表示拉伸，2表示旋转）。
• k_cs[i] 存储每个操作的参数（拉伸倍数或旋转角度）。

③ 查询处理：

• 对于每个查询，输入查询的区间 [left, right] 和初始坐标 (x, y)。
• 根据操作类型对坐标 (x, y) 进行拉伸或旋转变换。拉伸时直接将坐标乘以倍数，旋转时使用旋转矩阵进行变换。

④ 结果输出：输出每次查询变换后的坐标 (x, y)，保留三位小数。

代码实现

代码实现（思路一）：

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

int main(int argc, char const *argv[])
{
    // 输入 n 和 m
    // n表示操作的数量，m表示查询的次数
    int n, m;
    cin >> n >> m;

    // op数组表示每个操作的类型，1表示拉伸，2表示旋转
    // k_cs数组表示每个操作对应的参数（拉伸倍数或旋转角度）
    int op[n + 1];  // 操作类型数组，下标从1到n
    double k_cs[n + 1];  // 存储操作的参数（拉伸倍数或角度）

    // 输入 n 行，描述操作的类型和参数
    // 每行输入两个数：一个操作类型(1或2)，一个浮点数k（拉伸倍数或角度）
    for (int i = 1; i <= n; i++){
        cin >> op[i] >> k_cs[i];
    }

    int left, right;  // 查询区间的左右边界
    double x, y;      // 查询点的坐标

    // ans二维数组用于存储每次查询的结果，m表示查询的次数
    // 每次查询返回的结果包含 x 和 y 两个坐标
    vector<vector<double>> ans(m, vector<double>(2));

    // 对于每一个查询
    for (int j = 0; j < m; j++){
        // 输入查询区间[左边界，右边界]和查询点的坐标 (x, y)
        cin >> left >> right >> x >> y;

        // 对于指定区间内的每个操作
        for (int i = left; i <= right; i++){
            if (op[i] == 1){ // 如果是拉伸操作
                // 拉伸操作时，直接将x和y分别乘以拉伸倍数
                x = k_cs[i] * x;
                y = k_cs[i] * y;
            }
            else if (op[i] == 2) {  // 如果是旋转操作
                // 旋转操作时，需要用旋转矩阵进行变换
                double tmpx = x, tmpy = y;
                x = tmpx * cos(k_cs[i]) - tmpy * sin(k_cs[i]);
                y = tmpx * sin(k_cs[i]) + tmpy * cos(k_cs[i]);
            }
        }
        // 将查询结果存入ans数组
        ans[j][0] = x;
        ans[j][1] = y;
    }

    // 输出所有查询的结果，保留3位小数
    for (int i = 0; i < m; i++){
        cout << fixed << setprecision(3) << ans[i][0] << " " << ans[i][1] << endl;
    }

    return 0;
}

欢迎大家和我沟通交流(✿◠‿◠)