想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全

试题编号：202309-2
试题名称：坐标变换（其二）
时间限制：2.0s
内存限制：512.0MB
问题描述：

问题描述

对于平面直角坐标系上的坐标(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或θ），形如1k（表示拉伸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≤100000；

  • 输入的坐标均为整数且绝对值不超过1000000；

  • 单个拉伸操作的系数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 后可使用三角函数cos()和sin()。

  • Python：直接使用print(x)即可输出浮点数x；from math import cos, sin后可使用相应三角函数。

  • Java：建议使用double类型存储浮点数，可以使用System.out.print(x);进行输出；可使用Math.cos()和Math.sin()调用三角函数。

真题来源：坐标变换（其二）

感兴趣的同学可以如此编码进去进行练习提交

解题思路：

注意到一个操作是改变与原点的距离，一个操作是改变与xx轴所夹成的角度，如果考虑坐标在极坐标系下的表示形式，会发现这两种操作只是分别对其中一维进行操作，且这些操作是可逆的，且不会相互影响。

因此我们就预处理出op[i]表示操作1..i对距离rr和角度θ的影响，这是一个前缀和数组。

然后对于一个点问经过操作l..r的结果，先对它施加1..r操作的影响，再消除1..l−1操作的影响，即可得到l..r操作的结果。

施加影响，就是长度×k，角度+θ，消除影响，就是长度 /k，角度−θ。

最后根据r和θ还原出x=rcos⁡θ,y=rsin⁡θ。

时间复杂度为O(n+m)。

c++满分题解：

#include using namespace std; const double pi = acos(-1); int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;vector> op(n);for(auto &i : op){int opp;double k;cin >> opp >> k;if (opp == 1)i[0] = k;else{i[0] = 1;i[1] = k;}}for(int i = 1; i < n; ++ i){op[i][0] *= op[i - 1][0];op[i][1] += op[i - 1][1];}for(int i = 0; i > l >> r >> x >> y;-- l, -- r;double R = sqrt(1ll * x * x + 1ll * y * y), theta = 0;if (x == 0){if (y > 0)theta = pi / 2;else theta = -pi / 2;}else{theta = atan2(y, x);}R *= op[r][0];theta += op[r][1];if (l){R /= op[l - 1][0];theta -= op[l - 1][1];}cout << fixed << setprecision(10) << R * cos(theta) << ' ' << R * sin(theta) << '\n';}return 0;}

运行结果：