競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 189E

ABC189E

アフィン変換. 実装するときは,3次元の行列にした方が簡単. 行列は class にしておいた.
操作列は行列の列に対する積をとっておけばよい. つまり累積和を求めておけば,クエリ毎に O(3^3)で答えられる. ここで,3は行列の次数.

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {
  ll n;
  cin >> n;
  vll x(n), y(n);
  rep(i,n){
    cin >> x[i] >> y[i];
  }

  ll m; cin >> m;
  vector<Matrix<ll>> s(m+1, Matrix<ll>(3,3));
  s[0] = s[0].unit();
  rep(i,m){
    ll op; cin >> op;
    ll p;
    Matrix<ll> mat(3,3),
      r = vvll{
        {0,1,0},
        {-1,0,0},
        {0,0,1}
      };

    if(op == 1){
      mat = r.pow(3);
      // mat = r*r*r;
    }else if(op == 2){
      mat = r;      
    }else if(op == 3){
      cin >> p;
      mat = vvll{
        {-1,0,0},
        {0,1,0},
        {2*p,0,1}
      };
    }else{
      cin >> p;
      mat = vvll{
        {1,0,0},
        {0,-1,0},
        {0,2*p,1}
      };
    }

    s[i+1] = s[i] * mat;
  }
 
  ll q; cin >> q;
  rep(qi,q){
    ll a,b; cin >> a >> b;
    --b;

    Matrix<ll> v = vvll{
      {x[b],y[b],1}
    };

    Matrix<ll> ans = v*s[a];
    cout << ans.get(0,0) << " " << ans.get(0,1) << endl;
  }


  return 0;
}