本文主要是介绍Nyoj 298 点的变换[利用矩阵求解坐标点的转换，平移，绕原点旋转，沿x，y轴翻转]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：acm.nyist.net/JudgeOnline/problem.php?pid=298
题目的意思就是给你一n个点（n<=10000），求m次操作后（m<=1000000），各点变为什么了？操作有：平移，绕原点旋转，沿x，y轴翻转。
思路，利用矩阵相乘来解决。。这个很有意思。。
先来补充一下矩阵相乘的知识。。。。
First， 我们必须需要知道的是，矩阵相乘满足结合律，但是， 不满足交换律。。
接下来补充Matrix67大神总结的：
这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。
刚开始，没有理解他的精髓。。
以为每次每个操作都需要把每个点都变换，这样复杂度就是n*3*3*m了。。。O(mn)的复杂度。。。时间复杂度简直报表啊。。表示，理解错误了。。。。
我们根据结合律可以知道，m次操作是可以先结合的。。。最后求点的坐标。。3*3*3*m + n的复杂度。。时间复杂度O(m + n)的，可以接受的。。。
Code：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>using namespace std;const int N = 4;
const int M = 1e4 + 5;
const double PI = acos(-1);struct POINT
{double x, y;
} p[M];struct Matrix
{int n, m;double a[N][N];Matrix(){memset(a, 0, sizeof(a));}Matrix (int x, int y){n = x;m = y;memset(a, 0, sizeof(a));}
} ans;Matrix operator * (Matrix a, Matrix b)
{Matrix tans;tans.n = a.n;tans.m = b.m;for(int i = 1 ; i <= a.n; i ++){for(int j = 1; j <= b.m; j ++){for(int k = 1; k <= b.n; k ++)tans.a[i][j] += a.a[i][k] * b.a[k][j];}}return tans;
}Matrix Rotation(double r)// rotation, turn left ? turn right?
{Matrix op;op.n = 3;op.m = 3;op.a[1][1] = cos(r);op.a[1][2] = sin(r);op.a[2][1] = -sin(r);op.a[2][2] = cos(r);op.a[3][3] = 1;//trun by the base of (0, 0);return ans * op;
}Matrix go(double px, double py)
{Matrix op;op.n = 3;op.m = 3;op.a[1][1] = 1.0;op.a[2][2] = 1.0;op.a[3][3] = 1.0;op.a[3][1] = px;op.a[3][2] = py;return ans * op;
}Matrix bigger(double p)
{Matrix op;op.n = 3;op.m = 3;op.a[1][1] = p;op.a[2][2] = p;op.a[3][3] = 1;return ans * op;
}Matrix fx()
{Matrix op;op.n = 3;op.m = 3;op.a[1][1] = 1.0;op.a[2][2] = -1.0;op.a[3][3] = 1.0;return ans * op;
}Matrix fy()
{Matrix op;op.n = 3;op.m = 3;op.a[1][1] = -1.0;op.a[2][2] = 1.0;op.a[3][3] = 1.0;return ans * op;
}int main()
{
// freopen("1.txt", "r", stdin);int n, m;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i ++){scanf("%lf %lf", &p[i].x, &p[i].y);}getchar();ans.n= 3;ans.m = 3;for(int i = 1; i <= 3; i ++) ans.a[i][i] = 1.0;char order;for(int i = 1; i <= m; i ++){scanf("%c", &order);if(order == 'X') ans = fx();if(order == 'Y') ans = fy();if(order == 'M'){double tmpx, tmpy;cin >> tmpx >> tmpy;ans = go(tmpx, tmpy);}if(order == 'S'){double tmps;cin >> tmps;ans = bigger(tmps);}if(order == 'R'){double tmpr;cin >> tmpr;ans = Rotation(tmpr / 180.0 * PI);}getchar();}for(int i = 1; i <= n; i ++){printf("%.1lf %.1lf\n", p[i].x * ans.a[1][1] + p[i].y * ans.a[2][1] + ans.a[3][1], p[i].x * ans.a[1][2] + p[i].y * ans.a[2][2] + ans.a[3][2]);}return 0;
}代码虽然有点长，但是，直观性还是很好的。。
这篇关于Nyoj 298 点的变换[利用矩阵求解坐标点的转换，平移，绕原点旋转，沿x，y轴翻转]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
