目录

问题描述：

样例

问题解析

解决思想

引言

正题

问题描述：

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

  1. 拉伸 k倍：横坐标 x变为 kx，纵坐标 y变为 ky；

  2. 旋转 a：将坐标(x,y)绕坐标原点(0,0)逆时针旋转a弧度（0≤a<2*PI）。易知旋转后的横坐标为 xcos⁡(a)−ysin⁡(a)，纵坐标为 xsin⁡(a)+ycos⁡(a)。

设定好了包含n个操作的序列(t1,t2,⋯,tn)后，小 P 又定义了如下查询：

  • i j x y：坐标(x,y)经过操作 ti,⋯,tj（1≤i≤j≤n）后的新坐标。

对于给定的操作序列，试计算m个查询的结果。

样例

输入

10 52 0.592 4.9561 0.9971 1.3641 1.2421 0.822 2.8241 0.7162 0.1782 4.0941 6 -953188 -9466371 9 969538 8480814 7 -114758 5222231 9 -535079 6015978 8 159430 -511187

输出

-1858706.758 -83259.993-1261428.46 201113.678-75099.123 -738950.159-119179.897 -789457.532114151.88 -366009.892

问题解析

如果这道题纯粹采用暴力模拟的话会出现超时错误，输入n个操作之后储存在数组arr中，在m个样例中分别模拟一遍从第i步到第j步是导致这道题最后超时的原因

解决思想

如何优化的关键在于能否省去模拟从第i步到第j步的步骤

引言

首先我们来看一道问题：

给你一个数组，存在n个整数，共有m个样例，每个样例有i和j两个整数，请输出第i个数到第j个数的和。

这道题目一看十分简单，直接从将第i个数加到第j个数输出便可以完成，但是如果n，m的数量级很大，就会出现超时现象。

我们可以创建一个sum数组，sum[i]储存的是第一个元素到第i个元素之和，预处理之后我们求样例中的第i个数到第j个数便可以直接是sum[j]-sum[i-1]

正题

所以我们在csp的第二题中可以借鉴这道“前缀和”的题目解决模拟的耗时，且为方便计算时应当转化为极坐标系来看待，这样对长度，角度的变化也更容易实现

直接看代码：

#include#includeusing namespace std;//创建结构体point储存执行每步后所在的地点信息 struct point{//用极坐标表示 double len;double anl;};int main (){int n,m;cin>>n>>m;//P数组相当于前缀和的sum数组 point P[n+5];//初始化，伸缩1.0，转动0.0 P[0]={1.0,0.0}; for(int i=1;i>kind>>act;//伸缩 if(kind==1){//角度不变继承上一步 P[i].anl=P[i-1].anl;P[i].len=act*P[i-1].len; }else if(kind==2){P[i].len=P[i-1].len;P[i].anl=P[i-1].anl+act;}} //开始输入样例 for(int i=0;i>di>>dj>>dx>>dy;double clen=P[dj].len/P[di-1].len;//表示 第j步相对第i-1步伸缩的长度 double cagl=P[dj].anl-P[di-1].anl; //表示第j步相对第i-1步转动的角度 //开始代入公式dx*=clen;dy*=clen;double x=dx*cos(cagl)-dy*sin(cagl); double y=dx*sin(cagl)+dy*cos(cagl); printf("%f %f\n",x,y);}return 0;}