時間限制： 2.0 秒
空間限制： 512 MiB

題目背景：

對于平面直角坐標系上的坐標 (x,y)，小 P 定義了如下兩種操作：

1. 拉伸 k 倍：橫坐標 x 變為 kx，縱坐標 y 變為 ky；
2. 旋轉 θ：將坐標 (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

樣例輸出：

-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
由于具體計算方式不同，程序輸出結果可能與真實值有微小差異，樣例輸出僅保留了三位小數。

子任務：

80% 的測試數據滿足：n,m ≤ 1000；
全部的測試數據滿足：

• n,m≤10⁵；
• 輸入的坐標均為整數且絕對值不超過 10⁶；
• 單個拉伸操作的系數 k∈[0.5,2]；
• 任意操作區間 ti,?,tj（1 ≤ i ≤ j ≤ n）內拉伸系數 k 的乘積在 [0.001,1000] 范圍內。

評分方式

如果你輸出的浮點數與參考結果相比，滿足絕對誤差不大于 0.1，則該測試點滿分，否則不得分。

提示：

• C/C++：建議使用 double 類型存儲浮點數，并使用 scanf(“%lf”, &x); 進行輸入，printf(“%f”, x);
  輸出，也可以使用 cin 和 cout 輸入輸出浮點數；#include <math.h> 后可使用三角函數 cos() 和 sin()。
• Python：直接使用 print(x) 即可輸出浮點數 x；from math import cos, sin 后可使用相應三角函數。
• Java：建議使用 double 類型存儲浮點數，可以使用 System.out.print(x); 進行輸出；可使用
  Math.cos() 和 Math.sin() 調用三角函數。

解題思路：

思路一（哈希集合）：

1、解題步驟拆分：
① 輸入：首先輸入兩個整數 n 和 m，n 表示操作的數量，m 表示查詢的次數。接下來輸入 n 個操作及其參數，操作包括拉伸和旋轉。

② 操作存儲：

• op[i] 存儲每個操作的類型（1表示拉伸，2表示旋轉）。
• k_cs[i] 存儲每個操作的參數（拉伸倍數或旋轉角度）。

③ 查詢處理：

• 對于每個查詢，輸入查詢的區間 [left, right] 和初始坐標 (x, y)。
• 根據操作類型對坐標 (x, y) 進行拉伸或旋轉變換。拉伸時直接將坐標乘以倍數，旋轉時使用旋轉矩陣進行變換。

④ 結果輸出：輸出每次查詢變換后的坐標 (x, y)，保留三位小數。

代碼實現

代碼實現（思路一）：

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;int main(int argc, char const *argv[])
{// 輸入 n 和 m// n表示操作的數量，m表示查詢的次數int n, m;cin >> n >> m;// op數組表示每個操作的類型，1表示拉伸，2表示旋轉// k_cs數組表示每個操作對應的參數（拉伸倍數或旋轉角度）int op[n + 1];  // 操作類型數組，下標從1到ndouble k_cs[n + 1];  // 存儲操作的參數（拉伸倍數或角度）// 輸入 n 行，描述操作的類型和參數// 每行輸入兩個數：一個操作類型(1或2)，一個浮點數k（拉伸倍數或角度）for (int i = 1; i <= n; i++){cin >> op[i] >> k_cs[i];}int left, right;  // 查詢區間的左右邊界double x, y;      // 查詢點的坐標// ans二維數組用于存儲每次查詢的結果，m表示查詢的次數// 每次查詢返回的結果包含 x 和 y 兩個坐標vector<vector<double>> ans(m, vector<double>(2));// 對于每一個查詢for (int j = 0; j < m; j++){// 輸入查詢區間[左邊界，右邊界]和查詢點的坐標 (x, y)cin >> left >> right >> x >> y;// 對于指定區間內的每個操作for (int i = left; i <= right; i++){if (op[i] == 1){ // 如果是拉伸操作// 拉伸操作時，直接將x和y分別乘以拉伸倍數x = k_cs[i] * x;y = k_cs[i] * y;}else if (op[i] == 2) {  // 如果是旋轉操作// 旋轉操作時，需要用旋轉矩陣進行變換double tmpx = x, tmpy = y;x = tmpx * cos(k_cs[i]) - tmpy * sin(k_cs[i]);y = tmpx * sin(k_cs[i]) + tmpy * cos(k_cs[i]);}}// 將查詢結果存入ans數組ans[j][0] = x;ans[j][1] = y;}// 輸出所有查詢的結果，保留3位小數for (int i = 0; i < m; i++){cout << fixed << setprecision(3) << ans[i][0] << " " << ans[i][1] << endl;}return 0;
}

歡迎大家和我溝通交流(????)