CCF刷题计划——坐标变换（其二）（前缀和）

坐标变换（其二）

首先我按照一般的逻辑写出来，居然超时了？？？

之后想了想，还是觉得大有可为的，对拉伸前缀积，对旋转前缀和成功解决问题。

80分：超时

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N=1e5;struct Operate
{int op;double k;	
};int n,m;
vector<Operate>inst(N);void stretch(double&x,double&y,double&k)
{x=k*x;y=k*y;
}void rotate(double&x,double&y,double&k)
{//巨大坑点！！！计算旋转结果时要避免纵坐标受到横坐标已经计算从而变化的影响 double tempx=x; x=x*cos(k)-y*sin(k);y=tempx*sin(k)+y*cos(k);
}int main()
{cin>>n>>m;	//操作和查询次数Operate t;for(int i=1;i<=n;i++){cin>>t.op>>t.k;inst[i]=t;}double x,y,l,r;while(m--){cin>>l>>r>>x>>y;for(int i=l;i<=r;i++){ if(inst[i].op==1)stretch(x,y,inst[i].k);else if(inst[i].op==2)rotate(x,y,inst[i].k);}printf("%.3lf %.3lf\n",x,y);} return 0;} 

改进策略，我觉得伸缩是线性的变换，可能通过类似前缀和的方式进行规整。比如说，执行12345这五条指令，其中135都是伸缩指令，按理说，我们一共需要执行五次。如果使用类似前缀和的想法，我们只需要知道1、5这两次的前缀积，然后将k[5]/k[1-1]，就可以得到这部分总共需要处理的伸缩值了。

但是我发现这样还是有问题，因为为了判断旋转这种，还是会遍历一遍。那么，旋转，能类似前面的方式进行优化吗？如果不看公式，看角度的话，旋转其实也是一种线性的变化，无非是在前面的基础上进行加减罢了。我们可以累计这几步总共旋转了多少角度，最后再统一计算。

100昏：（一个坐标变换居然用上前缀和我是没想到的）

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N=1e5;int n,m;
//这里使用前缀和进行优化 
int inst[N]={0};
double mul_k[N]={1};
double angle[N]={0};void stretch(double&x,double&y,double k)
{x=k*x;y=k*y;
}void rotate(double&x,double&y,double k)
{//巨大坑点！！！计算旋转结果时要避免纵坐标受到横坐标已经计算从而变化的影响 double tempx=x; x=x*cos(k)-y*sin(k);y=tempx*sin(k)+y*cos(k);
}int main()
{cin>>n>>m;	//操作和查询次数int op;double k;for(int i=1;i<=n;i++){cin>>op>>k;if(op==1)	//在不同处理的同时需要对无关参数顺移 {mul_k[i]=mul_k[i-1]*k;angle[i]=angle[i-1];}else{mul_k[i]=mul_k[i-1];angle[i]=angle[i-1]+k;}}double x,y;int l,r;while(m--){cin>>l>>r>>x>>y;stretch(x,y,mul_k[r]/mul_k[l-1]);rotate(x,y,angle[r]-angle[l-1]);printf("%.3lf %.3lf\n",x,y);} return 0;}