LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@RubyLrving(ruby lrving)

abc189, E - Rotate and Flip, アフィン変換, 累積積

Last updated at Posted at 2021-01-26

前提知識として、二次関数、三角比、三角関数、行列、ベクトルの知識が必要になります。
私はここ１年間で集合、二次関数、三角比、確率、整数問題、図形の性質、三角関数、数列、行列、ベクトルを復習しています。

アフィン変換

2Dにおける平行移動、回転は以下の行列になります。

平行移動

\begin{pmatrix}
x' \\
y' \\
1
\end{pmatrix}
=
\begin{pmatrix}
1 & 0 & dx \\
0 & 1 & dy \\
0 & 0 & 1 \\
\end{pmatrix}
\begin{pmatrix}
x \\
y \\
1
\end{pmatrix}

回転

\begin{pmatrix}
x' \\
y' \\
1
\end{pmatrix}
=
\begin{pmatrix}
cosθ & -sinθ & 0 \\
sinθ & cosθ & 0 \\
0 & 0 & 1 \\
\end{pmatrix}
\begin{pmatrix}
x \\
y \\
1
\end{pmatrix}

直線 x=p について対称な位置に移動

(移動前x + 移動後X) / 2 = p \\
移動後X = 2p - 移動前x

E - Rotate and Flip

上記の知識を持って実装します。

C++
# include <bits/stdc++.h>
 
# define rep(i,n) for(int i=0; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
# define DegreesToRads( degrees ) ((degrees) * (M_PI/ 180.0f))
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
typedef struct {
    ll index[3];
} Matrix3X1;
 
typedef struct {
    ll index[3][3];
} Matrix3X3;
 
Matrix3X3 CreateFixed3X3Matrix(ll v){
    Matrix3X3 temp;
    rep(i, 3){
        rep(j, 3){
            temp.index[i][j] = v;
        }
    }
    return temp;
}
 
Matrix3X1 multiplyMatrixNxM(Matrix3X3 a, Matrix3X1 b){
    Matrix3X1 temp;
    temp.index[0] = 0; temp.index[1] = 0; temp.index[2] = 0;
 
    rep(i, 3){
        rep(j, 3){
            temp.index[i] += (a.index[i][j] * b.index[j]);
        }
    }
    return temp;
}
 
Matrix3X1 translate2DByMultiplication(Matrix3X1 start, ll dx, ll dy){
    Matrix3X3 temp;
    Matrix3X1 result;
 
    temp = CreateFixed3X3Matrix(0);
    temp.index[0][0] = 1;
    temp.index[1][1] = 1;
    temp.index[2][2] = 1;
 
    temp.index[0][2] = dx;
    temp.index[1][2] = dy;
 
    result = multiplyMatrixNxM(temp, start);
    return result;
}
 
Matrix3X1 Rotate2D(Matrix3X1 start, ll theta){
    Matrix3X3 temp;
    Matrix3X1 result;
 
    temp = CreateFixed3X3Matrix(0);
    temp.index[0][0] = cos(DegreesToRads(theta));
    temp.index[1][1] = cos(DegreesToRads(theta));
    temp.index[2][2] = 1;
    temp.index[0][1] = -1 * sin(DegreesToRads(theta));
    temp.index[1][0] = sin(DegreesToRads(theta));
 
    result = multiplyMatrixNxM(temp, start);
    return result;
}
 
int main() {
    int n;
    cin >> n;
 
    vector<vector<Matrix3X1>> piece(1, vector<Matrix3X1>(n));
    rep(i, n){
        cin >> piece[0][i].index[0] >> piece[0][i].index[1];
        piece[0][i].index[2] = 1;
    }
 
    int m;
    cin >> m;
    rep(i, m){
        int a, b;
        cin >> a;
 
        vector<Matrix3X1> copy = piece[i];
 
        if(a == 1){
            rep(j, n){
                copy[j] = Rotate2D(copy[j], 270);
            }
        }else if(a == 2){
            rep(j, n){
                copy[j] = Rotate2D(copy[j], 90);
            }
        }else if(a == 3){
            cin >> b;
            rep(j, n){
                copy[j] = translate2DByMultiplication(copy[j], (b - copy[j].index[0]) * 2, 0);
            }
        }else if(a == 4){
            cin >> b;
            rep(j, n){
                copy[j] = translate2DByMultiplication(copy[j], 0, (b - copy[j].index[1]) * 2);
            }
        } 
 
        piece.push_back(copy);
    }
 
    int q;
    cin >> q;
 
    rep(i, q){
        int a, b;
        cin >> a >> b;
        b--;
        cout << piece[a][b].index[0] << " " <<  piece[a][b].index[1] << endl;
    }
 
    return 0;
}

TLEになりました。
計算量はO(M^N+q)です。
ここで累積積という考え方が必要になります。
行列の合成（合成変換）を行っていきます。
q_a個目の操作という情報から変換行列を取り出し、q_b個目の最初の座標と計算すると答えが計算できるようになります。
計算量はO(N＋M＋Q)です。

C++
# include <bits/stdc++.h>

# define rep(i,n) for(int i=0; i<(n); ++i)
# define fixed_setprecision(n) fixed << setprecision((n))
# define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
# define pai 3.1415926535897932384
# define NUM_MAX 2e18
# define NUM_MIN -1e9
# define DegreesToRads( degrees ) ((degrees) * (M_PI/ 180.0f))

using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

typedef struct {
    ll index[3];
} Matrix3X1;

typedef struct {
    ll index[3][3];
} Matrix3X3;

Matrix3X3 CreateFixed3X3Matrix(ll v){
    Matrix3X3 temp;
    rep(i, 3){
        rep(j, 3){
            temp.index[i][j] = v;
        }
    }
    return temp;
}

Matrix3X1 multiplyMatrixNxM(Matrix3X3 a, Matrix3X1 b){
    Matrix3X1 temp;
    temp.index[0] = 0; temp.index[1] = 0; temp.index[2] = 0;

    rep(i, 3){
        rep(j, 3){
            temp.index[i] += (a.index[i][j] * b.index[j]);
        }
    }
    return temp;
}

Matrix3X3 multiply3X3Matrices(Matrix3X3 a, Matrix3X3 b)
{
    Matrix3X3 temp = CreateFixed3X3Matrix(0);

    for(int i = 0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                temp.index[i][j] += (a.index[i][k] * b.index[k][j]);
            }
        }
    }
    return temp;
}

Matrix3X3 translate2DByMultiplication(ll dx, ll dy){
    Matrix3X3 temp;

    temp = CreateFixed3X3Matrix(0);
    if(dy==0) temp.index[0][0] = -1;
    else temp.index[0][0] = 1;
    if(dx==0) temp.index[1][1] = -1;
    else temp.index[1][1] = 1;
    temp.index[2][2] = 1;

    temp.index[0][2] = dx;
    temp.index[1][2] = dy;

    return temp;
}

Matrix3X3 Rotate2D(ll theta){
    Matrix3X3 temp;

    temp = CreateFixed3X3Matrix(0);
    temp.index[0][0] = cos(DegreesToRads(theta));
    temp.index[1][1] = cos(DegreesToRads(theta));
    temp.index[2][2] = 1;
    temp.index[0][1] = -1 * sin(DegreesToRads(theta));
    temp.index[1][0] = sin(DegreesToRads(theta));

    return temp;
}

int main() {
    int n;
    cin >> n;

    vector<Matrix3X1> piece(n);
    rep(i, n){
        cin >> piece[i].index[0] >> piece[i].index[1];
        piece[i].index[2] = 1;
    }

    int m;
    cin >> m;
    
    vector<Matrix3X3> mat(1);
    mat[0].index[0][0] = 1;
    mat[0].index[1][1] = 1;
    mat[0].index[2][2] = 1;
    mat[0].index[0][2] = 0;
    mat[0].index[1][2] = 0;

    rep(i, m){
        int op;
        cin >> op;

        if(op == 1){
            Matrix3X3 m = Rotate2D(270);
            m = multiply3X3Matrices(m, mat.back());
            mat.push_back(m);
        }else if(op == 2){
            Matrix3X3 m = Rotate2D(90);
            m = multiply3X3Matrices(m, mat.back());
            mat.push_back(m);
        }else if(op == 3){
            int p;
            cin >> p;
            Matrix3X3 m = translate2DByMultiplication(2 * p, 0);
            m = multiply3X3Matrices(m, mat.back());
            mat.push_back(m);
        }else{
            int p;
            cin >> p;
            Matrix3X3 m = translate2DByMultiplication(0, 2 * p);
            m = multiply3X3Matrices(m, mat.back());
            mat.push_back(m);
        }
    }
   
    int q;
    cin >> q;

    rep(i, q){
        int a, b;
        cin >> a >> b;
        b--;

        Matrix3X1 m = multiplyMatrixNxM(mat[a], piece[b]);
        cout << m.index[0] << " " <<  m.index[1] << endl;
    }

    return 0;
}

感想

この問題が簡単になってD問題などになったら解けそうです。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?