NYOJ 298 点的变换

　　这题放在矩阵快速幂里，我一开始想不透它是怎么和矩阵搭上边的，然后写了个暴力的果然超时，上网看了题解后，发现竟然能够构造一些精巧的矩阵来处理，不得不说实在太强大了！ http://blog.csdn.net/lyhvoyage/article/details/39755595

　　然后我的代码是：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<iostream>
  6 using namespace std;
  7 #define For(i,s,t)    for(int i=s; i<=t; ++i)
  8 const double pi= acos(-1.0);
  9 
 10 struct matrix{
 11     int r,c;
 12     double a[5][5];
 13     matrix(): r(3),c(3){
 14         memset(a,0,sizeof(a));
 15         a[3][3]= 1.0;
 16     }
 17     matrix(char ch){
 18         new (this)matrix();
 19         if(ch=='x' || ch=='X'){
 20             a[1][1]= 1.0;
 21             a[2][2]= -1.0;
 22         }
 23         else if(ch=='y' || ch== 'Y'){
 24             a[2][2]= 1.0;
 25             a[1][1]= -1.0;
 26         }
 27         else if(ch=='E'){
 28             a[1][1]= a[2][2]= 1.0;
 29         }
 30     }
 31     matrix(double p, char ch){
 32         new (this)matrix();
 33         if(ch=='s' || ch== 'S'){
 34             a[1][1]= a[2][2]= p;
 35         }
 36         else if(ch=='r' || ch=='R'){
 37             a[1][1]= a[2][2]= cos(p);
 38             a[1][2]= sin(p);
 39             a[2][1]= -sin(p);
 40         }
 41     }
 42     matrix(double dx, double dy, char ch){
 43         if(ch=='p'|| ch=='P'){
 44             new (this)matrix();
 45             r= 1;
 46             a[1][1]= dx;
 47             a[1][2]= dy;
 48             a[1][3]= 1.0;
 49         }
 50         else if(ch=='M' || ch=='m'){
 51             new (this)matrix();
 52             a[1][1]= a[2][2]= 1.0;
 53             a[3][1]= dx;
 54             a[3][2]= dy;
 55         }
 56     }
 57     matrix operator *(const matrix &m2) const {
 58         matrix mul;
 59         mul.r= r;
 60         mul.c= m2.c;
 61         mul.a[3][3]= 0.0;
 62         For(i,1,r)    For(j,1,m2.c)    For(k,1,c)
 63             mul.a[i][j]+= a[i][k]*m2.a[k][j];
 64         return mul;    
 65     }
 66 } point[10005];
 67 
 68 int main()
 69 {
 70     int n,m;
 71     scanf("%d%d",&n,&m);
 72     double x,y;
 73     for(int i=1; i<=n; ++i){
 74         scanf("%lf %lf",&x,&y);
 75         point[i]= matrix(x,y,'p');
 76     }
 77     matrix ans('E');
 78     while(m--){
 79         char ch;
 80         cin>>ch;
 81         if(ch =='X')    ans= ans*matrix('X');
 82         else if(ch=='Y')    ans= ans*matrix('Y');
 83         else if(ch=='M'){
 84             double dx,dy;
 85             scanf("%lf %lf",&dx,&dy);
 86             ans= ans*matrix(dx,dy,'M');
 87         }
 88         else if(ch=='S'){
 89             double p;
 90             scanf("%lf",&p);
 91             ans= ans*matrix(p,'S');
 92         }
 93         else if(ch=='R'){
 94             double rad;
 95             scanf("%lf",&rad);
 96             rad= rad/180*pi;
 97             ans= ans*matrix(rad,'R');
 98         }
 99     }
100     for(int i=1; i<=n; ++i){
101         point[i]= point[i]*ans;
102         printf("%.1f %.1f
",point[i].a[1][1],point[i].a[1][2]);
103     }
104     return 0;
105 }

View Code

　　还是第一次写了超过100行的代码，调试了好久了，唉~~

　　然后，稍微作了下更改，还有另一个版本的：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<cstdlib>
  5 using namespace std;
  6 #define For(i,s,t)    for(int i=s; i<=t; ++i)
  7 const double pi= acos(-1.0);
  8 
  9 struct matrix{
 10     int r,c;
 11     double a[5][5];
 12     void init(int r=3, int c=3){
 13         this->r = r;
 14         this->c = c;
 15         memset(a,0,sizeof(a));
 16         a[3][3]= 1.0;
 17     }
 18     matrix() {    init();    }
 19     matrix(char ch){
 20         init();
 21         if(ch=='x' || ch=='X'){
 22             a[1][1]= 1.0;
 23             a[2][2]= -1.0;
 24         }
 25         else if(ch=='y' || ch== 'Y'){
 26             a[2][2]= 1.0;
 27             a[1][1]= -1.0;
 28         }
 29         else if(ch=='E'){
 30             a[1][1]= a[2][2]= 1.0;
 31         }
 32     }
 33     matrix(double p, char ch){
 34         init();
 35         if(ch=='s' || ch== 'S'){
 36             a[1][1]= a[2][2]= p;
 37         }
 38         else if(ch=='r' || ch=='R'){
 39             a[1][1]= a[2][2]= cos(p);
 40             a[1][2]= sin(p);
 41             a[2][1]= -sin(p);
 42         }
 43     }
 44     matrix(double dx, double dy, char ch){
 45         if(ch=='p'|| ch=='P'){
 46             init(1,3);
 47             a[1][1]= dx;
 48             a[1][2]= dy;
 49             a[1][3]= 1.0;
 50         }
 51         else if(ch=='M' || ch=='m'){
 52             init();
 53             a[1][1]= a[2][2]= 1.0;
 54             a[3][1]= dx;
 55             a[3][2]= dy;
 56         }
 57     }
 58     matrix operator *(const matrix &m2) const {
 59         matrix mul;
 60         mul.init(r,m2.c);
 61         mul.a[3][3]= 0.0;
 62         For(i,1,r)    For(j,1,m2.c)    For(k,1,c)
 63             mul.a[i][j]+= a[i][k]*m2.a[k][j];
 64         return mul;    
 65     }
 66 } point[10005];
 67 
 68 int main()
 69 {
 70     int n,m;
 71     scanf("%d%d",&n,&m);
 72     double x,y;
 73     for(int i=1; i<=n; ++i){
 74         scanf("%lf %lf",&x,&y);
 75         point[i]= matrix(x,y,'p');
 76     }
 77     matrix ans('E');
 78     while(m--){
 79         getchar();
 80         char ch= getchar();
 81         if(ch =='X')    ans= ans*matrix('X');
 82         else if(ch=='Y')    ans= ans*matrix('Y');
 83         else if(ch=='M'){
 84             double dx,dy;
 85             scanf("%lf %lf",&dx,&dy);
 86             ans= ans*matrix(dx,dy,'M');
 87         }
 88         else if(ch=='S'){
 89             double p;
 90             scanf("%lf",&p);
 91             ans= ans*matrix(p,'S');
 92         }
 93         else if(ch=='R'){
 94             double rad;
 95             scanf("%lf",&rad);
 96             rad= rad/180*pi;
 97             ans= ans*matrix(rad,'R');
 98         }
 99     }
100     for(int i=1; i<=n; ++i){
101         point[i]= point[i]*ans;
102         printf("%.1f %.1f
",point[i].a[1][1],point[i].a[1][2]);
103     }
104     return 0;
105 }

View Code