點的變換

時間限制：2000?ms ?|? 內存限制：65535?KB 難度：5 描述

平面上有不超過10000個點，坐標都是已知的，現在可能對所有的點做以下幾種操作：

平移一定距離(M)，相對X軸上下翻轉(X)，相對Y軸左右翻轉(Y),坐標縮小或放大一定的倍數(S),所有點對坐標原點逆時針旋轉一定角度(R)。????

操作的次數不超過1000000次，求最終所有點的坐標。

?

提示：如果程序中用到PI的值，可以用acos(-1.0)獲得。

輸入

只有一組測試數據
測試數據的第一行是兩個整數N,M，分別表示點的個數與操作的個數(N<=10000,M<=1000000)
隨后的一行有N對數對，每個數對的第一個數表示一個點的x坐標，第二個數表示y坐標，這些點初始坐標大小絕對值不超過100。
隨后的M行，每行代表一種操作，行首是一個字符：
首字符如果是M,則表示平移操作，該行后面將跟兩個數x,y，表示把所有點按向量(x,y)平移;
首字符如果是X，則表示把所有點相對于X軸進行上下翻轉;
首字符如果是Y，則表示把所有點相對于Y軸進行左右翻轉;
首字符如果是S，則隨后將跟一個數P,表示坐標放大P倍;
首字符如果是R，則隨后將跟一個數A,表示所有點相對坐標原點逆時針旋轉一定的角度A(單位是度)

輸出

每行輸出兩個數，表示一個點的坐標(對結果四舍五入到小數點后1位，輸出一位小數位）
點的輸出順序應與輸入順序保持一致

樣例輸入

2 5 1.0 2.0 2.0 3.0 X Y M 2.0 3.0 S 2.0 R 180

樣例輸出

-2.0 -2.0 0.0 0.0

分析：如果按照題目描述的那樣模擬，肯定會超時。這時就要找一種快速變換的方法。

這樣就可以先算出經過M次變換后形成的最終矩形，然后用點的坐標乘以矩形就可以求出答案。

#include <cstdio> #include <cstring> #include <cmath> #define PI acos(-1.0)struct Matrix {double mat[3][3];Matrix() {memset(mat, 0, sizeof(mat));for(int i = 0; i < 3; i++)mat[i][i] = 1;}Matrix Multi(Matrix A, Matrix B) {Matrix res;for(int i = 0; i < 3; i++) {for(int j = 0; j < 3; j++) {res.mat[i][j] = 0;for(int k = 0; k < 3; k++) {res.mat[i][j] = res.mat[i][j] + A.mat[i][k] * B.mat[k][j];}}}return res;}Matrix Translation(Matrix A, double p, double q) { //向上平移p個單位，向右平移q個單位Matrix res;res.mat[0][2] = p;res.mat[1][2] = q;return Multi(res, A);}Matrix Scale(Matrix A, double p) { //縮放p倍Matrix res;res.mat[0][0] = res.mat[1][1] = p;return Multi(res, A);}Matrix Turn_UD(Matrix A) { //坐標軸上下翻轉Matrix res;res.mat[1][1] = -1;return Multi(res, A);}Matrix Turn_LR(Matrix A) { //坐標軸左右翻轉Matrix res;res.mat[0][0] = -1;return Multi(res, A);}Matrix Rotate(Matrix A, double angle) { //繞原點逆時針旋轉angle角度double rad = angle / 180.0 * PI;Matrix res;res.mat[0][0] = cos(rad); res.mat[0][1] = -sin(rad);res.mat[1][0] = sin(rad); res.mat[1][1] = cos(rad);return Multi(res, A);} };struct Point {double x, y; } P[10005];int main() {int n, m;char op[5];double x, y;scanf("%d%d", &n, &m);for(int i = 0; i < n; i++)scanf("%lf%lf", &P[i].x, &P[i].y);Matrix A;for(int i = 0; i < m; i++) {scanf("%s", op);if(op[0] == 'X') A = A.Turn_UD(A);else if(op[0] == 'Y') A = A.Turn_LR(A);else if(op[0] == 'M') {scanf("%lf%lf", &x, &y);A = A.Translation(A, x, y);}else if(op[0] == 'S') {scanf("%lf", &x);A = A.Scale(A, x);}else if(op[0] == 'R') {scanf("%lf", &x);A = A.Rotate(A, x);}}for(int i = 0; i < n; i++) {double xx = A.mat[0][0] * P[i].x + A.mat[0][1] * P[i].y + A.mat[0][2];double yy = A.mat[1][0] * P[i].x + A.mat[1][1] * P[i].y + A.mat[1][2];printf("%.1lf %.1lf\n", xx, yy);}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 298 点的变换（矩阵快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。