Computer vision: Build a transform from steps

Real transforms are built from simple steps. Combine them into one matrix.

What to build

A program that composes translations, scalings and rotations into one affine matrix.

Requirements

  • Steps are translate tx ty, scale sx sy and rotate deg (about the origin: x' = cos θ x − sin θ y, y' = sin θ x + cos θ y). They are applied in the order given.
  • The result is M = Sₙ × … × S₂ × S₁. Print its first two rows, three decimal places per entry.
  • Round each entry to three decimal places and add 0.0 before printing, so that no entry prints as -0.000.

Input

Line 1: N. Then N lines, one step each.

Output

Two lines of three values.

Constraints

N ≤ 20.

Example

Input:

2
scale 2 2
translate 3 -1

Output:

2.000 0.000 3.000
0.000 2.000 -1.000

Why it works

Multiplying each new step on the left applies it after everything before it, so one matrix reproduces the whole sequence; order matters because matrix products do not commute.

Examples

Example 1 · Input
2
scale 2 2
translate 3 -1
Expected output
2.000 0.000 3.000
0.000 2.000 -1.000
Example 2 · Input
2
translate 3 -1
scale 2 2
Expected output
2.000 0.000 6.000
0.000 2.000 -2.000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Keep a 3 × 3 matrix M, starting as the identity. For each step build its 3 × 3 matrix S and set M = S × M.

Hint 2

Rotation uses `math.radians`, and entries cos θ, −sin θ in the first row and sin θ, cos θ in the second.

Solution

Show one correct solution (try it yourself first)
import math


def mul(A, B):
    return [[sum(A[i][k] * B[k][j] for k in range(3)) for j in range(3)] for i in range(3)]


M = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
for _ in range(int(input())):
    op = input().split()
    if op[0] == "translate":
        S = [[1, 0, float(op[1])], [0, 1, float(op[2])], [0, 0, 1]]
    elif op[0] == "scale":
        S = [[float(op[1]), 0, 0], [0, float(op[2]), 0], [0, 0, 1]]
    else:
        a = math.radians(float(op[1]))
        S = [[math.cos(a), -math.sin(a), 0], [math.sin(a), math.cos(a), 0], [0, 0, 1]]
    M = mul(S, M)
for row in M[:2]:
    print(" ".join(f"{round(v, 3) + 0.0:.3f}" for v in row))

Lesson: Affine transforms: shift, scale, rotate and warp →