CSP202309-2坐标变换，怎么优化啊，超时，80分

Question

CSP202309-2 坐标变换（二）

#include<iostream>
#include<cmath>
using namespace std;
struct opera{
    int id;
    double k;
}a[100010];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d%lf",&a[i].id,&a[i].k);
    }
    while(m--){
        int start,end;
        double x,y;
        scanf("%d%d%lf%lf",&start,&end,&x,&y);
        for(int i=start;i<=end;i++){
            if(a[i].id==1){
                x*=a[i].k;
                y*=a[i].k;
            } else {
                double t=x;
                double cs=cos(a[i].k),sn=sin(a[i].k);
                x=t*cs-y*sn;
                
                y=t*sn+y*cs;
            }
        }
        printf("%.3f %.3f\n",x,y);
    }
}

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

优化坐标变换的代码主要可以从以下几个方面入手：

1. 减少不必要的计算：在旋转操作中，如果连续进行多次旋转操作，可以考虑累积旋转角度，而不是每次都进行旋转计算。这样可以减少计算量。同样，对于拉伸操作也可以考虑累积拉伸系数。

2. 使用高精度计算：由于涉及到浮点数计算，特别是多次乘除和三角函数的计算，可能会产生累积误差。可以使用更高精度的计算方法或者库来减少误差。例如，使用专门的数学库来处理浮点数运算。

3. 并行化计算：如果操作序列和查询可以并行处理，那么可以利用多核处理器或者并行计算框架来加速计算。例如，可以分配不同的查询给不同的线程或进程处理。

针对你的代码，可以尝试以下优化建议：

• 在处理查询时，不必每次都重新计算拉伸和旋转的结果。可以维护一个累积的拉伸系数和旋转角度，然后一次性应用这些变换到查询坐标上。这样减少了不必要的计算步骤。
• 考虑使用高精度库来处理浮点数运算，避免由于浮点数运算误差导致的精度问题。
• 如果操作序列和查询量非常大，可以考虑使用多线程或并行处理来加速计算。不过这需要评估硬件资源是否充足以及并行化的复杂性是否值得投入。

此外，还可以考虑使用预编译指令来加速代码的执行（对于C++），确保关键部分代码的优化（例如使用内联函数等）。还可以考虑对算法逻辑进行优化，避免不必要的复杂性和冗余计算。