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

本题中操作共有n个，坐标共有m个。观察数据规模，n和m均<=100000，因此时间复杂度为O(n*m)的暴力算法就不要尝试了，纯粹是浪费宝贵的时间。

对于每个给出的坐标，题目需要我们求经过i ~ j步操作变换后得到的结果。只考虑存在拉伸操作的情况下，最终拉伸的系数等于每次拉伸操作系数的乘积。只考虑存在旋转操作的情况下，最终旋转的角度等于每次旋转操作角度的和。因为拉伸操作和旋转操作是互不影响的，因此可以使用两个数组分别存储拉伸操作的前缀积以及旋转操作的前缀和。对于每个坐标给出的i ~ j步操作，利用拉伸操作的前缀积数组以及旋转操作的前缀和数组快速求出拉伸系数和旋转角度即可。

#include #include using namespace std;int main(){int n, m;scanf("%d %d", &n, &m);double stretchPrefix[n + 1] = {1}, rotatePrefix[n + 1] = {0}; //拉伸操作的前缀积，旋转操作的前缀和for (int ni = 0; ni < n; ++ni) {int type;double val;scanf("%d %lf", &type, &val);switch (type) {case 1:stretchPrefix[ni + 1] = val * stretchPrefix[ni];rotatePrefix[ni + 1] = rotatePrefix[ni];break;case 2:stretchPrefix[ni + 1] = stretchPrefix[ni];rotatePrefix[ni + 1] = val + rotatePrefix[ni];break;default:break;}}for (int mi = 0; mi < m; ++mi) {int i, j;double x, y;scanf("%d %d %lf %lf", &i, &j, &x, &y);double k = stretchPrefix[j] / stretchPrefix[i - 1]; //求经过了i~j步的操作后的拉伸系数double theta = rotatePrefix[j] - rotatePrefix[i - 1]; //求经过了i~j步操作后的旋转角度double x1 = k * x;double y1 = k * y;double x2 = x1 * cos(theta) - y1 * sin(theta);double y2 = x1 * sin(theta) + y1 * cos(theta);printf("%lf %lf\n", x2, y2);}return 0;}