Phân tích: Scaled Triangle

Trong bài toán này, chúng ta được cho một tam giác và một tam giác khác có được bằng cách áp dụng một phép biến đổi affine lên tam giác thứ nhất -- bao gồm dịch chuyển, xoay và thay đổi tỉ lệ. Chúng ta được yêu cầu tìm một điểm cố định (fixed point) cho phép biến đổi này.

Đây thực chất là một trường hợp đặc biệt của "Định lý điểm cố định Banach" (Banach's fixed point theorem), đảm bảo sự tồn tại và duy nhất của các điểm cố định cho một số ánh xạ tự thân của không gian metric, mặc dù việc biết định lý này không phải là yêu cầu bắt buộc để giải bài.

Để giải quyết bài toán này, chúng ta cần tìm các tham số của phép biến đổi.

Các phép biến đổi như vậy rất quen thuộc với bất kỳ ai từng làm việc với đồ họa máy tính. Để xem xét phép biến đổi như một toán tử tuyến tính, việc sử dụng tọa độ thuần nhất (homogeneous coordinates) là rất thuận tiện, trong đó mặt phẳng của chúng ta được nhúng vào mặt phẳng \(z=1\) trong không gian 3D. Tức là, coi mỗi điểm \((x, y)\) là \((x, y, 1)\). (Lưu ý: Như thường lệ, tất cả các vector tương ứng với các điểm được coi là vector cột, mặc dù chúng ta viết chúng theo hàng ngang ở đây.) Trong thiết lập này, việc xoay một điểm một góc \(\alpha\) quanh điểm \((0, 0)\) tương ứng với việc nhân vector \(v = (x, y, 1)\) với ma trận

Dịch chuyển một điểm \((x, y)\) một khoảng \((dx, dy)\) tương ứng với việc nhân \(v\) với

và phép co giãn tâm tại \(0\) với hệ số \(s\) tương ứng với việc nhân \(v\) với

Phép biến đổi tổng thể trông như sau:

v' = T R S v = M v.

Lưu ý rằng ở trên chúng ta tập trung vào tác động của phép biến đổi trên mặt phẳng \(z=1\). Người đọc quan tâm có thể xác minh rằng nó ánh xạ mọi mặt phẳng nằm ngang \(z=z_0\) vào chính nó.

Để tìm ma trận \(M\), chúng ta có thể giải riêng lẻ cho các ma trận \(T, R\), và \(S\). Tuy nhiên có một cách dễ dàng hơn. Từ các ràng buộc đầu vào, chúng ta biết rằng điểm \(A\) được ánh xạ tới \(A'\), \(B\) tới \(B'\) và \(C\) tới \(C'\). Coi mỗi điểm là một vector trong mặt phẳng \(z=1\), sao cho \(A, B, C\) độc lập tuyến tính. Do đó, ma trận \(3 \times 3\) \([A B C]\) là khả nghịch. Vì vậy, phương trình:

M [A B C] = [A' B' C']

có một nghiệm duy nhất cho \(M\).

Từ đây, vẫn có hai cách để giải bài toán của chúng ta:

1. Cách tiếp cận lặp: Một quan sát là nếu chúng ta áp dụng phép biến đổi và có một điểm không thay đổi, chúng ta có thể áp dụng nó liên tục trên tam giác kết quả và điểm đó vẫn sẽ giữ nguyên. Vì vậy, chúng ta áp dụng phép biến đổi này cho đến khi tam giác trở nên rất nhỏ. Điểm cố định sẽ luôn nằm bên trong tam giác, vì vậy chúng ta có thể dừng lại khi độ dài các cạnh của tam giác hiện tại nhỏ hơn độ chính xác cần thiết.
2. Cách tiếp cận đại số: Chúng ta xem xét lại phương trình. Chúng ta biết có một điểm duy nhất \(v = (x, y, 1)\) sao cho \(Mv = v\). Từ đây chúng ta biết rằng (i) \(1\) phải là một giá trị riêng (eigen-value) của ma trận \(M\); (ii) không gian của các vector riêng tương ứng với \(1\) phải là một chiều. Vì vậy, chúng ta chỉ cần giải hệ phương trình \((M - I)v = 0\), và tìm giao điểm của không gian nghiệm (một đường thẳng) với mặt phẳng \(z=1\).

Thông tin thêm

• Định lý điểm cố định Banach
• Tọa độ thuần nhất
• Giá trị riêng và vector riêng

Dựa trên phân tích chính thức của Google Code Jam.