Yukicoder No.471 直列回転機
CTFのcrypto問でよく見る感じがする。
解法はすぐだったが、名前衝突させてTypeError
と入力形式のミスで$2$WA生やした。
solution
平行移動 + 回転 + 平行移動 を繰り返すので、全体としてAffine変換。 以下のような形なので、$3$回クエリを投げれば$6$本の方程式が得られ変換が特定できる。
\[\begin{pmatrix} x' \\\\ y' \\\\ 1 \\\\ \end{pmatrix} = \begin{pmatrix} a & b & e \\\\ c & d & f \\\\ 0 & 0 & 1 \\\\ \end{pmatrix} \begin{pmatrix} x \\\\ y \\\\ 1 \\\\ \end{pmatrix}\]implementation
#!/usr/bin/env python3
import sys
m = int(input())
x = [ None ] * m
y = [ None ] * m
for i in range(m):
x[i], y[i] = map(int, input().split())
def ask(x, y):
print('?', x, y)
sys.stdout.flush()
fx, fy = map(int, input().split())
return fx, fy
# [ x' ] [ a b e ] [ x ]
# [ y' ] = [ c d f ] [ y ]
# [ 1 ] [ 0 0 1 ] [ 1 ]
ae, cf = ask(1, 0)
aae, ccf = ask(2, 0)
a = aae - ae
e = ae - a
c = ccf - cf
f = cf - c
be, df = ask(0, 1)
b = be - e
d = df - f
def rotate(x, y):
fx = a*x + b*y + e
fy = c*x + d*y + f
return fx, fy
print('!')
for i in range(m):
print(*rotate(x[i], y[i]))