首页 > ACM题库 > HDU-杭电 > HDU 4087-ALetter to Programmers[解题报告]HOJ
2015
04-16

HDU 4087-ALetter to Programmers[解题报告]HOJ

ALetter to Programmers

问题描述 :

Dear Programmers:
I can imagine how surprised you are when you receive this strange letter. Well, be patient, I am going to talk about some really exciting things that you must be interested in.
First of all, I have to congratulate everyone of you – the gifted programmers, for you are so lucky to have a God-given chance to be my inheritor – a new Deity of Stars. However, you know that it is difficult for an ordinary person to become a deity, so only the best one among you can finally be chosen. Therefore, you are facing a hard test for estimating your abilities.
Try your best to compete!
The Deity of Stars, of course, is the unique dominator of all stars in the whole universe, which means controlling the stars’ tracks and ensuring that the stars move in their own orbit are his/her most important responsibilities. What? You will be sick in managing incalculable stars? Don’t worry, it will be a piece of cake once you have a wonderful tool – a special kind of programming language. That is why I am going to choose my inheritor from you.
So in your test, you will be given a special program and the initial positions of some stars (In deities’ eyes, the stars are so small that they can be regarded as points), you need to figure out the new positions of these stars after the program is executed.
Considering all of you are green hands, I will just give you a program in a simple
version during the test, which contains only several kinds of instructions listed below:
1. translate tx ty tz
Everything in (x, y, z) must be moved to ( x+tx, y+ty, z+tz)
2. scale a b c
Everything in (x, y, z) will be moved to (ax, by, cz)
3. rotate a b c d
It will make everything rotate. The rotation axis is the straight line from (0, 0, 0) to (a, b, c), and the angle of rotation is d (measured in degrees). If you stand at (a, b, c) and look at (0, 0, 0),you will see that the rotation is counterclockwise.
4. repeat k
The instructions between a "repeat" instruction and an "end" instruction matched with it (will be explained later) will be executed for k times. The integer k is non-negative and a 32-bit signed integer is sufficient to deal with it.
5. end
If there are some unmatched "repeat" instructions, the "end" instruction will be matched with the nearest unmatched "repeat" instruction before it; otherwise, it indicates the end of the program. Please note that a repeat-end pair may include other repeat-end pairs.
Now the test is coming. Are you ready?
Good Luck,
Zi Wei, Emperor of North Polaris

输入:

The input contains no more than 20.
Each test case begins with one integer n (1 <= n <= 1000), indicating the number of the given points. Then there is a correct program without any extra blanks or redundant characters and it contains less than 100 lines. Each line contains only one instruction. Then n lines follow, each containing three numbers which indicate the coordinates of a po int in 3D universe. All numbers except n and k are floats and no more than 1000 in absolute value.
Two consecutive cases are separated by a blank line.
The input ends with n = 0.

输出:

The input contains no more than 20.
Each test case begins with one integer n (1 <= n <= 1000), indicating the number of the given points. Then there is a correct program without any extra blanks or redundant characters and it contains less than 100 lines. Each line contains only one instruction. Then n lines follow, each containing three numbers which indicate the coordinates of a po int in 3D universe. All numbers except n and k are floats and no more than 1000 in absolute value.
Two consecutive cases are separated by a blank line.
The input ends with n = 0.

样例输入:

2 
rotate 1.0 1.0 1.0 90.0
translate 2.0 2.0 2.0
end
1.0 1.0 1.0
1.0 0.0 0.0

3
repeat 100
translate 2.7 -0.2 1.1
translate -2.6 0.0 -1.0
end
scale 1.0 0.0 0.5
end
0.5 2.7 1.1
0.22 0 7.0
1.2 3.4 5.6

0

样例输出:

3.00 3.00 3.00
2.33 2.91 1.76

10.50 0.00 5.55
10.22 0.00 8.50
11.20 0.00 7.80

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define EPS 1e-10
#define MAX(a,b) ((a)>(b)?(a):(b))
const double pi = acos( -1.0 );
using namespace std;

int tc, ren[105], tr;
double SqS2( double x, double y )
{
    return sqrt( x*x + y*y );
}
struct CO
{
    char c[12];
    double x[5];
    int en, r;
} co[105];
struct MA
{
    double m[4][4];
} sa;
void Mul( MA &x, double p[4] )
{
    int i, j;
    double t[4];
    for( i = 0; i < 4; i ++ )
        t[i] = p[i];
    for( i = 0; i < 4; i ++ )
    {
        p[i] = 0;
        for( j = 0; j < 4; j ++ )
            p[i] += x.m[i][j] * t[j];
    }
}
MA Mul( MA &x, MA &y )
{
    MA a;
    int i, j, k;
    for( i = 0; i < 4; i ++ )
        for( j = 0; j < 4; j ++ )
        {
            a.m[i][j] = 0;
            for( k = 0; k < 4; k ++ )
                a.m[i][j] += x.m[i][k] * y.m[k][j];
        }
    return a;
}
MA Mi( MA &x, int m )
{
    int i, j;
    MA a;
    if( m == 0 )
    {
        for( i = 0; i < 4; i ++ )
            for( j = 0; j < 4; j ++ )
                a.m[i][j] = sa.m[i][j];
        return a;
    }
    if( m == 1 )
    {
        for( i = 0; i < 4; i ++ )
            for( j = 0; j < 4; j ++ )
                a.m[i][j] = x.m[i][j];
        return a;
    }
    a = Mi( x, m>>1 );
    a = Mul( a, a );
    if( m & 1 )
        a = Mul( a, x );
    return a;
}
MA GetM( int l, int r )
{
    int i, j, k;
    double t, t1;
    MA a, b, mz, mx, mz0;
    for( i = 0; i < 4; i ++ )
        for( j = 0; j < 4; j ++ )
            a.m[i][j] = sa.m[i][j];
    for( i = l; i <= r; i ++ )
    {
        if( co[i].c[0] == 'r' && co[i].c[1] == 'e' )  //re
        {
            if( co[i].en > i+1 && co[i].r > 0 )
            {
                b = GetM( i+1, co[i].en-1 );
                b = Mi( b, co[i].r );
                a = Mul( b, a );
            }
            i = co[i].en;
        }
        else if( co[i].c[0] == 'r' )   //ro
        {
			if( co[i].x[3] == 0 )
				continue;
            for( k = 0; k < 4; k ++ )
                for( j = 0; j < 4; j ++ )
                    mz0.m[k][j] = mz.m[k][j] = mx.m[k][j] = sa.m[k][j];
            t = SqS2( co[i].x[0], co[i].x[1] );
            mz.m[0][0] = mz.m[1][1] = co[i].x[0] / t;
            mz.m[0][1] = co[i].x[1] / t;
            mz.m[1][0] = -mz.m[0][1];
            t1 = SqS2( t, co[i].x[2] );
            mx.m[0][0] = mx.m[2][2] = co[i].x[2] / t1;
            mx.m[2][0] = t / t1;
            mx.m[0][2] = -mx.m[2][0];
            mz0.m[0][0] = mz0.m[1][1] = cos( co[i].x[3]/180 * pi );
            mz0.m[1][0] = sin( co[i].x[3]/180 * pi );
            mz0.m[0][1] = -mz0.m[1][0];
            b = Mul( mx, mz );
            b = Mul( mz0, b );
            mz.m[1][0] = -mz.m[1][0];
            mz.m[0][1] = -mz.m[0][1];
            mx.m[0][2] = -mx.m[0][2];
            mx.m[2][0] = -mx.m[2][0];
            b = Mul( mx, b );
            b = Mul( mz, b );
            a = Mul( b, a );
        }
        else if( co[i].c[0] == 's' )   //scale
            for( j = 0; j < 3; j ++ )
                for( k = 0; k < 4; k ++ )
                    a.m[j][k] *= co[i].x[j];
        else if( co[i].c[0] == 't' )   //trans
            for( j = 0; j < 3; j ++ )
                a.m[j][3] += co[i].x[j];
    }
    return a;
}

int main()
{
    int n, i, j;
    double p[4];
    for( i = 0; i < 4; i ++ )
        for( j = 0; j < 4; j ++ )
            sa.m[i][j] = 0;
    for( i = 0; i < 4; i ++ )
        sa.m[i][i] = 1;
    MA mm;
    while( ~scanf( "%d", &n ) && n )
    {
        tc = tr = 0;
        while( tr >= 0 )
        {
            scanf( "%s", co[tc].c );
            if( co[tc].c[0] == 'e' )    //end
            {
                if( tr > 0 )
                    co[ ren[tr-1] ].en = tc;
                tr --;
            }
            else if( co[tc].c[0] == 'r' && co[tc].c[1] == 'e' )  //re
            {
                ren[tr++] = tc;
                scanf( "%d", &( co[tc].r ) );
            }
            else if( co[tc].c[0] == 'r' )   //ro
                for( i = 0; i < 4; i ++ )
                    scanf( "%lf", (co[tc].x)+i );
            else
                for( i = 0; i < 3; i ++ )
                    scanf( "%lf", (co[tc].x)+i );
            tc ++;
        }
		if( tc > 1 )
	        mm = GetM( 0, tc-2 );
		for( i = 0; i < n; i ++ )
        {
            for( j = 0; j < 3; j ++ )
                scanf( "%lf", p+j );
			if( tc > 1 )
			{
				p[3] = 1;
				Mul( mm, p );
			}
			for( j = 0; j < 3; j ++ )
				if( p[j] <= 0 && p[j] > -0.005 )
					p[j] = 0;
            printf( "%.2lf %.2lf %.2lf\n", p[0], p[1], p[2] );
        }
        printf( "\n" );
    }
    return 0;
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }