关于矩阵的经典操作1,那就是坐标的变换
通过二维空间或者三维空间,给定n个点,m 个操作,构造O(m+n)的算法输出m个操作后各点的位置,操作有平移、缩放、翻转和旋转
参考:十个利用矩阵乘法解决的经典题目
在三维空间中就是扩张一下就可以了,只是在三维空间的旋转,如果给定的是角度,那么就要注意公式如下:
因此要注意一下,这是针对角度和坐标点
HDU3320
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3320
题意描述:给定坐标(1,1,,,1),求经过若干操作后的坐标位置
在这儿先是把初始点构造单位矩阵,在没进过一个操作就利用矩阵来实现
#include<iostream> #include<iomanip> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<climits> #define maxn 10000 using namespace std; struct matrix { double a[4][4]; void clear() { memset(a,0,sizeof(a)); } matrix operator +(const matrix &b)const { matrix c; c.clear(); for(int i=0; i<4; i++) { for(int j=0; j<4; j++) { c.a[i][j]=a[i][j]+b.a[i][j]; } } return c; } matrix operator *(const matrix &b)const { matrix c; c.clear(); for(int i=0; i<4; i++) { for(int j=0; j<4; j++) { for(int k=0; k<4; k++) { c.a[i][j]+=a[i][k]*b.a[k][j]; } } } return c; } }; int t; double x,y,z,angle; char str1[100],str2[100]; double num[4]; int main() { //freopen("C:\\Users\\Administrator\\Desktop\\in.txt" , "r" , stdin); scanf("%d",&t); while(t--) { matrix b={ 1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1 }; scanf("%s",str1); scanf("%s",str2); while(str2[2]!='E') { switch(str2[2]) { case 'T': { sscanf(str2+12,"(%lf,%lf,%lf);",&x,&y,&z); matrix temp= { 1,0,0,x, 0,1,0,y, 0,0,1,z, 0,0,0,1 }; b=b*temp; break; } case 'S': { sscanf(str2+8,"(%lf,%lf,%lf);",&x,&y,&z); matrix temp= { x,0,0,0, 0,y,0,0, 0,0,z,0, 0,0,0,1 }; b=b*temp; break; } case 'R': { sscanf(str2+9,"(%lf,%lf,%lf,%lf);",&angle,&x,&y,&z); double s=sin(angle),c=cos(angle); double k=sqrt(x*x+y*y+z*z); x/=k;y/=k;z/=k; matrix temp= { x*x*(1-c)+c,x*y*(1-c)-z*s,x*z*(1-c)+y*s,0, y*x*(1-c)+z*s,y*y*(1-c)+c,y*z*(1-c)-x*s,0, x*z*(1-c)-y*s,y*z*(1-c)+x*s,z*z*(1-c)+c,0, 0,0,0,1 }; b=b*temp; break; } case 'V': { sscanf(str2+10,"(%lf,%lf,%lf);",&num[0],&num[1],&num[2]); } } scanf("%s",str2); } printf("%.1lf %.1lf %.1lf\n", b.a[0][0]*num[0]+b.a[0][1]*num[1]+b.a[0][2]*num[2]+b.a[0][3], b.a[1][0]*num[0]+b.a[1][1]*num[1]+b.a[1][2]*num[2]+b.a[1][3], b.a[2][0]*num[0]+b.a[2][1]*num[1]+b.a[2][2]*num[2]+b.a[2][3]); } return 0; }
关于在读入数据时用sscanf()来读入就行了,关于这个函数,如果不懂,那么就百度一下
HDU4087
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4087
这个题比较蛋疼,主要是读入数据比较麻烦,其他的操作没啥
在读入时只要用额外的数组来辅助
#include<iostream> #include<iomanip> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<climits> #define maxn 10000 using namespace std; const double pi=acos(-1.0); const double eps = 1e-6; int sig(double d) { return (d > eps) - (d < -eps); } struct matrix { double mat[4][4]; void init()//µ¥Î»¾ØÕó { memset(mat, 0, sizeof(mat)); for (int i = 0; i < 4; i++) mat[i][i] = 1.0; } void clear() { memset(mat, 0, sizeof(mat)); } void transose()//转置 { for (int i = 0; i < 4; i++) for (int j = i + 1; j < 4; j++) { swap(mat[i][j], mat[j][i]); } } matrix operator +(const matrix &b)const { matrix c; c.clear(); for(int i=0; i<4; i++) { for(int j=0; j<4; j++) { c.mat[i][j]=mat[i][j]+b.mat[i][j]; } } return c; } matrix operator *(const matrix &b)const { matrix c; c.clear(); for(int i=0; i<4; i++) { for(int j=0; j<4; j++) { for(int k=0; k<4; k++) { c.mat[i][j]+=mat[i][k]*b.mat[k][j]; } } } return c; } }; matrix operator ^(matrix a,int b) { matrix ans; ans.init(); while(b) { if(b&1) { ans=ans*a; } a=a*a; b>>=1; } return ans; } int repeat[55555]; matrix M[55555]; int main() { //freopen("C:\\Users\\Administrator\\Desktop\\in.txt" , "r" , stdin); int n; while (cin >> n && n) { string op; M[0].init(); int top = 0; while (cin >> op) { if (op == "end") { if (top == 0) break; else { M[top - 1] = M[top - 1] * (M[top] ^ repeat[top]); top--; } } if (op == "rotate") { double x, y, z, angle; scanf("%lf%lf%lf%lf", &x, &y, &z, &angle); matrix tmp; angle = angle / 180 * pi; double m = sqrt(x*x + y*y + z*z); double s=sin(angle),c=cos(angle); x /= m; y /= m; z /= m; tmp.mat[0][0] = x * x * (1 - c) + c; tmp.mat[0][1] = x * y * (1 - c) - z * s; tmp.mat[0][2] = x * z * (1 - c) + y * s; tmp.mat[0][3]=0; tmp.mat[1][0] = x * y * (1 - c) + z * s; tmp.mat[1][1] = y * y * (1 - c) + c; tmp.mat[1][2] = y * z * (1 - c) - x * s; tmp.mat[1][3]=0; tmp.mat[2][0] = x * z * (1 - c) - y * s; tmp.mat[2][1] = y * z * (1 - c) + x * s; tmp.mat[2][2] = z * z * (1 - c) + c; tmp.mat[2][3]=0; tmp.mat[3][0]=0; tmp.mat[3][1]=0; tmp.mat[3][2]=0; tmp.mat[3][3] = 1.0; tmp.transose(); M[top] = M[top] * tmp; } if (op == "repeat") { top++; scanf("%d", &repeat[top]); M[top].init(); } if (op == "translate") { double x, y, z; scanf("%lf%lf%lf", &x, &y, &z); matrix tmp; tmp.init(); tmp.mat[0][3] = x; tmp.mat[1][3] = y; tmp.mat[2][3] = z; tmp.transose(); M[top] = M[top] * tmp; } if (op == "scale") { double x, y, z; scanf("%lf%lf%lf", &x, &y, &z); matrix tmp; tmp.init(); tmp.mat[0][0] = x; tmp.mat[1][1] = y; tmp.mat[2][2] = z; tmp.transose(); M[top] = M[top] * tmp; } } for (int i = 0; i < n; i++) { matrix input; memset(input.mat, 0, sizeof(input.mat)); scanf("%lf%lf%lf", &input.mat[0][0], &input.mat[0][1], &input.mat[0][2]); input.mat[0][3] = 1.0; matrix ret; for (int i = 0; i < 1; i++) for (int j = 0; j < 4; j++) { ret.mat[i][j] = 0; for (int k = 0; k < 4; k++) ret.mat[i][j] += input.mat[i][k] * M[0].mat[k][j]; } for (int i = 0; i < 4; i++) if (sig(ret.mat[0][i]) == 0) ret.mat[0][i] = 0.0; printf("%.2f %.2f %.2f\n", ret.mat[0][0], ret.mat[0][1], ret.mat[0][2]); } puts(""); } return 0; }
这个题目也可以用stack来模拟数据的读入过程,只是这样做比较麻烦