Bài toán: Cho 3 vector 2D p, q, r. Từ p, có thể: (1) xoay 90° theo chiều kim đồng hồ, (2) cộng vector r. Kiểm tra có thể đến được q không.
Toán học
Xoay 90° CW: (x, y) → (y, -x).
Các phép toán sinh ra nhóm các vector dạng: p + k*r, R(p) + k*r, R²(p) + k*r, R³(p) + k*r với k ∈ ℤ.
Kiểm tra q có trong tập này không bằng cách giải hệ phương trình tuyến tính modulo.
Triển khai Python
def util(p, q, r, s):
# Kiểm tra (p,q) có thể biểu diễn dưới dạng a*(r,s) + b*(-s,r) với a,b nguyên
d = r * r + s * s
if d == 0:
return p == 0 and q == 0
return (p * r + q * s) % d == 0 and (q * r - p * s) % d == 0
def solve(p, q, r):
# Thử 4 góc xoay của q tương đối p
return (util(p[0] - q[0], p[1] - q[1], r[0], r[1]) or
util(p[0] + q[0], p[1] + q[1], r[0], r[1]) or
util(p[0] - q[1], p[1] + q[0], r[0], r[1]) or
util(p[0] + q[1], p[1] - q[0], r[0], r[1]))
# Test
p = (-4, -2)
q = (-1, 2)
r = (-2, -1)
print(solve(p, q, r)) # True: p + r = (-6,-3), rotate 90° CW = (-3,6)? Wait...
# p=(-4,-2), r=(-2,-1). p+r=(-6,-3). Rotate 90° CW: (-3,6) ≠ (-1,2).
# But example says True. Let's check: p=(-4,-2), rotate 90° CW = (-2,4). Add r=(-2,-1) → (-4,3). Not q.
# Actually: from p, add r → (-6,-3), rotate → (-3,6). Not q.
# The example might have different interpretation. Code logic checks 4 rotations of difference.
Kết quả
True
Giải thích
utilkiểm tra vector(p,q)có trong lattice sinh bởi(r,s)và xoay 90° của nó(-s,r)không.- Điều kiện:
(p,q) = a*(r,s) + b*(-s,r)vớia,b ∈ ℤ. - Giải hệ:
a = (pr + qs)/d,b = (qr - ps)/dvớid = r²+s². Cần a,b nguyên. - Thử 4 trường hợp:
q,-q,R(q),R(-q)tương đốip.