坐标变换（其二）题解(CSP202309-02)-循序渐进

问题描述

对于平面直角坐标系上的坐标 (x,y)，小 P 定义了如下两种操作：

拉伸 k 倍：横坐标 x 变为 kx，纵坐标 y 变为 ky；
旋转 θ：将坐标 (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 或 θ），形如 1 k（表示拉伸 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

Data

样例输出

-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

由于具体计算方式不同，程序输出结果可能与真实值有微小差异，样例输出仅保留了三位小数。

题解：

第一种方法就是纯纯的模拟,这里只需注意旋转和拉伸是两个独立的操作,可以积累起所有的角度和拉伸长度，然后分别进行一次旋转和拉伸操作,代码如下:、

80Point Code

#include<cstdio>
#include<cmath>
int kind[100001];
double operation[100001];
int l,r,n,m;
double k,rotate,x,y,_x,_y;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%lf",&kind[i],&operation[i]);
	}
	for(int i=1;i<=m;i++){
		k=1;rotate=0;
		scanf("%d%d%lf%lf",&l,&r,&x,&y);
		for(int j=l;j<=r;j++){
			if(kind[j]==1)
				k*=operation[j];
			else
				rotate+=operation[j];
		}
		_x=x*cos(rotate)-y*sin(rotate);
		_y=x*sin(rotate)+y*cos(rotate);
		_x*=k;
		_y*=k;
		printf("%lf %lf\n",_x,_y);
	}
	return 0;
}

不出意外的话就会出意外

回过头来分析暴力的代码，代码最好时的部分其实是下面这块

for(int i=1;i<=m;i++){
		k=1;rotate=0;
		scanf("%d%d%lf%lf",&l,&r,&x,&y);
		for(int j=l;j<=r;j++){
			if(kind[j]==1)
				k*=operation[j];
			else
				rotate+=operation[j];
		}
		_x=x*cos(rotate)-y*sin(rotate);
		_y=x*sin(rotate)+y*cos(rotate);
		_x*=k;
		_y*=k;
		printf("%lf %lf\n",_x,_y);
	}

每执行一次查询，都会遍历执行[l-r]之间的操作，如何优化呢

这里我们想到了前缀和，与其遍历[l-r]之间的操作，不如定义分别一个k[i]和rotate[i]函数分别表示执行操作[1-i]后的拉伸长度和旋转角度，那么执行[l-r]之间的操作就变成了k[r]/k[l-1],rotate[r]-rotate[l-1]。

注意

1. 这里是i-1,而不是i，因为k[i-1]（rotate[i-1]）数组作用是抵消[1-i-1]的操作，不要抵消操作i

2. k数组抵消要用除法，rotate数组用减法

而后我又建立了k_qian和rotate_qian数组用来映射，以k为例，k_qian[i]表示原操作序列中[1-i]之间执行了多少次关于拉伸的操作，具体代码如下:

AC Code

#include<cstdio>
#include<cmath>
int n,m,l,r,_l,_r,ktot=0,rotate_tot=0;
double lengthen,rotate,x,y,_x,_y,temp;
int kind[100001];
double now_k[100001];
double now_rotate[100001];
int k_qian[100001];
int rotate_qian[100001];
int main(){
	now_k[0]=1;now_rotate[0]=0;
	k_qian[0]=0;rotate_qian[0]=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&kind[i]);
		scanf("%lf",&temp);
		if(kind[i]==1){
			ktot++;
			now_k[ktot]=now_k[ktot-1]*temp;
		}
		else{
			rotate_tot++;
			now_rotate[rotate_tot]=now_rotate[rotate_tot-1]+temp;
		}
		k_qian[i]=ktot;
		rotate_qian[i]=rotate_tot;
	} 
	for(int i=1;i<=m;i++){

		scanf("%d%d%lf%lf",&l,&r,&x,&y);
	    _l=k_qian[l-1];
	    _r=k_qian[r]; 
	    lengthen=now_k[_r]/now_k[_l];
	    _l=rotate_qian[l-1];
	    _r=rotate_qian[r];
	    rotate=now_rotate[_r]-now_rotate[_l];
	    _x=x*cos(rotate)-y*sin(rotate);
	    _y=x*sin(rotate)+y*cos(rotate);
	    _x*=lengthen;
	    _y*=lengthen;
		printf("%f %f\n",_x,_y);
	}
	return 0;
}

制作不易，感谢支持！

Korloa