CCF-CSP真题《202309-2 坐标变换（其二）》思路+python，c++满分题解

妖狐艹你老母 2024-02-19 08:31 18阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202309-2</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>坐标变换（其二）</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>2.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>问题描述</h3> <p>对于平面直角坐标系上的坐标&nbsp;(x,y)，小 P 定义了如下两种操作：</p> 
    <ol> 
     <li> <p>拉伸&nbsp;k&nbsp;倍：横坐标&nbsp;x&nbsp;变为&nbsp;kx，纵坐标&nbsp;y&nbsp;变为&nbsp;ky；</p> </li> 
     <li> <p>旋转&nbsp;θ：将坐标&nbsp;(x,y)&nbsp;绕坐标原点&nbsp;(0,0)&nbsp;<strong>逆时针</strong>旋转&nbsp;θ&nbsp;弧度（0≤θ&lt;2π）。易知旋转后的横坐标为&nbsp;xcos⁡θ−ysin⁡θ，纵坐标为&nbsp;xsin⁡θ+ycos⁡θ。</p> </li> 
    </ol><p>设定好了包含&nbsp;n&nbsp;个操作的序列&nbsp;(t1,t2,⋯,tn)&nbsp;后，小 P 又定义了如下查询：</p> 
    <ul> 
     <li><code>i j x y</code>：坐标&nbsp;(x,y)&nbsp;经过操作&nbsp;ti,⋯,tj（1≤i≤j≤n）后的新坐标。</li> 
    </ul><p>对于给定的操作序列，试计算&nbsp;m&nbsp;个查询的结果。</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>输入共&nbsp;n+m+1&nbsp;行。</p> <p>输入的第一行包含空格分隔的两个正整数&nbsp;n&nbsp;和&nbsp;m，分别表示操作和查询个数。</p> <p>接下来&nbsp;n&nbsp;行依次输入&nbsp;n&nbsp;个操作，每行包含空格分隔的一个整数（操作类型）和一个实数（k&nbsp;或&nbsp;θ），形如&nbsp;1&nbsp;k（表示拉伸&nbsp;k&nbsp;倍）或&nbsp;2&nbsp;θ（表示旋转&nbsp;θ）。</p> <p>接下来&nbsp;m&nbsp;行依次输入&nbsp;m&nbsp;个查询，每行包含空格分隔的四个整数&nbsp;i、j、x&nbsp;和&nbsp;y，含义如前文所述。</p> <h3>输出格式</h3> <p>输出到标准输出中。</p> <p>输出共&nbsp;m&nbsp;行，每行包含空格分隔的两个实数，表示对应查询的结果。</p> <h3>样例输入</h3> 
    <blockquote> 
     <p>10 5<br> 2 0.59<br> 2 4.956<br> 1 0.997<br> 1 1.364<br> 1 1.242<br> 1 0.82<br> 2 2.824<br> 1 0.716<br> 2 0.178<br> 2 4.094<br> 1 6 -953188 -946637<br> 1 9 969538 848081<br> 4 7 -114758 522223<br> 1 9 -535079 601597<br> 8 8 159430 -511187</p> 
    </blockquote> <h3>样例输出</h3> 
    <blockquote> 
     <p>-1858706.758 -83259.993<br> -1261428.46 201113.678<br> -75099.123 -738950.159<br> -119179.897 -789457.532<br> 114151.88 -366009.892</p> 
    </blockquote> <h3>样例说明</h3> <p>第五个查询仅对输入坐标使用了操作八：拉伸&nbsp;0.716&nbsp;倍。</p> <p>横坐标：159430×0.716=114151.88</p> <p>纵坐标：−511187×0.716=−366009.892</p> <p>由于具体计算方式不同，程序输出结果可能与真实值有微小差异，样例输出仅保留了三位小数。</p> <h3>评测用例规模与约定</h3> <p>80%&nbsp;的测试数据满足：n,m≤1000；</p> <p>全部的测试数据满足：</p> 
    <ul> 
     <li> <p>n,m≤100000；</p> </li> 
     <li> <p>输入的坐标均为整数且绝对值不超过&nbsp;1000000；</p> </li> 
     <li> <p>单个拉伸操作的系数&nbsp;k∈[0.5,2]；</p> </li> 
     <li> <p>任意操作区间&nbsp;ti,⋯,tj（1≤i≤j≤n）内拉伸系数&nbsp;k&nbsp;的乘积在&nbsp;[0.001,1000]&nbsp;范围内。</p> </li> 
    </ul><h3>评分方式</h3> <p>如果你输出的浮点数与参考结果相比，满足绝对误差不大于&nbsp;0.1，则该测试点满分，否则不得分。</p> <h3>提示</h3> 
    <ul> 
     <li> <p>C/C++：建议使用&nbsp;<code>double</code>&nbsp;类型存储浮点数，并使用&nbsp;<code>scanf("%lf", &amp;x);</code>&nbsp;进行输入，<code>printf("%f", x);</code>&nbsp;输出，也可以使用&nbsp;<code>cin</code>&nbsp;和&nbsp;<code>cout</code>&nbsp;输入输出浮点数；<code>#include &lt;math.h&gt;</code>&nbsp;后可使用三角函数&nbsp;<code>cos()</code>&nbsp;和&nbsp;<code>sin()</code>。</p> </li> 
     <li> <p>Python：直接使用&nbsp;<code>print(x)</code>&nbsp;即可输出浮点数&nbsp;<code>x</code>；<code>from math import cos, sin</code>&nbsp;后可使用相应三角函数。</p> </li> 
     <li> <p>Java：建议使用&nbsp;<code>double</code>&nbsp;类型存储浮点数，可以使用&nbsp;<code>System.out.print(x);</code>&nbsp;进行输出；可使用&nbsp;<code>Math.cos()</code>&nbsp;和&nbsp;<code>Math.sin()</code>&nbsp;调用三角函数。</p> </li> 
    </ul></td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[坐标变换（其二）][Link 1]

> 感兴趣的同学可以如此编码进去进行练习提交

**解题思路：**

> 注意到一个操作是改变与原点的距离，一个操作是改变与xx轴所夹成的角度，如果考虑坐标在极坐标系下的表示形式，会发现这两种操作只是分别对其中一维进行操作，且这些操作是可逆的，且不会相互影响。
> 
> 因此我们就预处理出 op\[i\]表示操作 1..i对距离 rr和角度 θ的影响，这是一个前缀和数组。
> 
> 然后对于一个点问经过操作 l..r的结果，先对它施加1..r操作的影响，再消除 1..l−1操作的影响，即可得到 l..r操作的结果。
> 
> 施加影响，就是长度 ×k，角度 +θ，消除影响，就是长度 /k，角度−θ。
> 
> 最后根据r和 θ还原出x=rcos⁡θ,y=rsin⁡θ。
> 
> 时间复杂度为 O(n+m)。

**c++满分题解：**

#include <bits/stdc++.h>
    using namespace std;
     
    const double pi = acos(-1);
     
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n, m;
        cin >> n >> m;
        vector<array<double, 2>> op(n);
        for(auto &i : op){
            int opp;
            double k;
            cin >> opp >> k;
            if (opp == 1)
                i[0] = k;
            else{
                i[0] = 1;
                i[1] = k;
            }
        }
        for(int i = 1; i < n; ++ i){
            op[i][0] *= op[i - 1][0];
            op[i][1] += op[i - 1][1];
        }
        for(int i = 0; i < m; ++ i){
            int l, r, x, y;
            cin >> l >> r >> x >> y;
            -- l, -- r;
            double R = sqrt(1ll * x * x + 1ll * y * y), theta = 0;
            if (x == 0){
                if (y > 0)
                    theta = pi / 2;
                else 
                    theta = -pi / 2;
            }else{
                theta = atan2(y, x);
            }
            R *= op[r][0];
            theta += op[r][1];
            if (l){
                R /= op[l - 1][0];
                theta -= op[l - 1][1];
            }
            cout << fixed << setprecision(10) << R * cos(theta) << ' ' << R * sin(theta) << '\n';
        }
        return 0;
    }

**运行结果：**

![47a201c89b424cb1bff222f62bd117ce.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T174
[47a201c89b424cb1bff222f62bd117ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/7224c5a433364578a6130de0b7ecd1eb.png