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;
 }