算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

   定义一种变换向量的语言,其语法有这么几种:
      1. translate tx ty tz  功能:(x,y,z) = (x+tx,y+ty,z+tz)
      2. scale a b c         功能:(x,y,z) = (ax,by,cz)
      3. rotate tx ty tz angle  功能:让x,y,z以tx,ty,tz为轴逆时针旋转angle。
      4. rotate k .... end   功能: 重复执行...k次
    给若干个向量,输出对应的变换后的向量。

吐槽:

    1. 注意-0.0的情况。
    2. 样例过了基本就过了。

算法分析:

    因为语法4,所以不难想到要使用矩阵来变换向量。
    2的矩阵变换都比较直观,3的矩阵变换有公式。
    关键是1的变换矩阵我纠结了好久。
    其实把矩阵变成4×4就可以了
        1  0  0  0
        0  1  0  0
        0  0  1  0
        tx ty tz 1
    最后用[x,y,z,1]去乘最终变换矩阵就可以了。。。
  1 #include<iostream>
  2 #include<cmath>
  3 #include<cstdio>
  4 #include<string>
  5 using namespace std;
  6 const int N = 4;
  7 struct matrix {
  8     double num[N][N];
  9     matrix (double a){
 10         for(int i=0;i<N;i++)
 11             for(int j=0;j<N;j++)
 12                 num[i][j] = (i==j)*a;
 13     }
 14     matrix(double x,double y,double z){
 15         for(int i=0;i<N;i++)
 16             for(int j=0;j<N;j++)
 17                 num[i][j] = (i==j)*1.0;
 18         num[3][0] = x;
 19         num[3][1] = y;
 20         num[3][2] = z;
 21     }
 22     matrix(double x,double y,double z, int X){
 23         for(int i=0;i<N;i++)
 24             for(int j=0;j<N;j++)
 25                 num[i][j] =(i==j)*1.0;
 26         num[0][0] = x; num[1][1] = y; num[2][2] = z;
 27     }
 28     matrix(double P[3],double ang){
 29         for(int i=0;i<N;i++)
 30             for(int j=0;j<N;j++) num[i][j] = (i==j)*1.0;
 31         double flag [3][3] = {0,1.0,-1.0,-1.0,0,1.0,1.0,-1.0,0}, sum = P[0] + P[1] + P[2];
 32         for(int i=0;i<3;i++)
 33             for(int j=0;j<3;j++) if(i == j)
 34                 num[i][j] = P[i]*P[i] + (1-P[i]*P[i]) * cos(ang);
 35                 else num[i][j] = P[i]*P[j]*(1-cos(ang)) + (sum - P[i] - P[j]) * sin(ang) * flag[i][j];
 36     }
 37 };
 38 matrix operator * (const matrix& a, const matrix& b){
 39     matrix c(0.0);
 40     for(int i=0; i<N; i++)
 41         for(int j=0; j<N; j++)
 42             for(int k = 0; k<N; k++)
 43                 c.num[i][j] += a.num[i][k] * b.num[k][j];
 44     return c;
 45 }
 46 matrix pow(matrix a, int b){
 47     matrix ans(1.0), t = a;
 48     while(b) {
 49         if(b&1) ans = ans * t;
 50         t = t * t; b>>=1;
 51     }
 52     return ans;
 53 }
 54 const double pi = acos(-1.0);
 55 matrix dfs(){
 56     matrix ans(1.0);
 57     string cmd;
 58     int k; double x,y,z,a;
 59     for(;;){
 60         cin >> cmd;
 61         if(cmd=="end") return ans;
 62         else if(cmd=="repeat"){
 63             scanf("%d",&k);
 64             matrix temp = dfs();
 65             temp = pow(temp, k);
 66             ans = ans * temp;
 67         }
 68         else {
 69             scanf("%lf%lf%lf",&x,&y,&z);
 70             if(cmd == "translate"){
 71                 matrix temp(x, y, z); ans = ans * temp;
 72             }
 73             else if(cmd == "scale"){
 74                 matrix temp(x, y, z, 0); ans = ans * temp;
 75             }
 76             else {
 77                 scanf("%lf",&a);
 78                 a = a/180.0*pi;
 79                 double sum = sqrt(x*x + y*y +z*z);
 80                 double p[3] = {x/sum, y/sum, z/sum};
 81                 matrix temp(p,a); ans = ans * temp;
 82             }
 83         }
 84     }
 85 }
 86 double pre(double x){
 87     return x + 1e-6;
 88 }
 89 int main(){
 90     int n;
 91     while(~scanf("%d",&n) && n){
 92         matrix t = dfs();
 93         double x,y,z,px,py,pz;
 94         while(n--){
 95             scanf("%lf%lf%lf",&x,&y,&z);
 96             px = x*t.num[0][0] + y*t.num[1][0] +z*t.num[2][0] + t.num[3][0];
 97             py = x*t.num[0][1] + y*t.num[1][1] +z*t.num[2][1] + t.num[3][1];
 98             pz = x*t.num[0][2] + y*t.num[1][2] +z*t.num[2][2] + t.num[3][2];
 99             printf("%.2lf %.2lf %.2lf\n",pre(px),pre(py),pre(pz));
100         }
101         puts("");
102     }
103 }
104 
posted on 2012-06-24 16:01 西月弦 阅读(379) 评论(1)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: hdu 4087 仿射几何 + 矩阵乘法[未登录]
2012-06-26 00:04 | David
这个为什么叫做仿射几何呢?  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理