Test Set 1: quay quanh trục \(z\)

Đây là bài hình học kiến thiết ad hoc với nhiều cách giải. Giả sử ban đầu khối lập phương song song các trục. Quay nó quanh trục \(z\) một góc \(t\), từ \(+x\) về \(+y\), rồi xét bóng.

Các nhận xét chính:

• Bóng là hình chữ nhật song song các trục \(x,z\); tại \(t=0\) nó là hình vuông.
• Với \(0\le t\le\pi/4\), chiều theo \(z\) luôn bằng 1, còn chiều theo \(x\) là \(V_x-W_x\), trong đó \(V,W\) là hai đỉnh biên. Vì vậy đây thực chất là bài hai chiều và có thể bỏ qua \(z\).
• Do \(W_x=-V_x\), diện tích bóng là \(A=1\cdot(V_x-W_x)=2V_x\).

Diện tích lớn nhất trong họ này đạt tại \(t=\pi/4\), khi \(V_x=\sqrt{1/2}\), nên \(A=\sqrt2\approx1.414214\), bao trùm toàn bộ Test Set 1. Từ hình học cơ bản,

Đảo công thức một cách ngây thơ cho tổng của \(\pi/4\) và \(\arccos(A/\sqrt2)\), nhưng để giữ \(0\le t\le\pi/4\) phải chọn nhánh âm:

Một tâm mặt bất biến là \((0,0,1/2)\). Quay \((1/2,0)\) và \((0,1/2)\) trong mặt phẳng \(xy\) cho hai tâm còn lại:

Test Set 2: từ bóng nhỏ nhất tới bóng lớn nhất

Hai nhận xét quyết định là:

• bóng nhỏ nhất là hình vuông khi một mặt song song với mặt phẳng \(xz\);
• bóng lớn nhất là lục giác đều khi một đỉnh nằm trên trục \(y\).

Để đơn giản hóa tính toán, trước hết quay khối \(45^\circ\) quanh trục \(y\); chiều quay không quan trọng vì cho cùng một tư thế đối xứng. Khối khi ấy vẫn có bóng nhỏ nhất. Tiếp theo quay quanh trục \(x\), từ \(+z\) về \(+y\), cho tới khi một đỉnh \(H\) chạm trục \(y\). Diện tích bóng tăng liên tục và đơn điệu trong suốt chuyển động, từ \(\sqrt2\) tới \(\sqrt3\). Do đó mọi diện tích trung gian đều đạt được và có thể tìm góc bằng tìm kiếm nhị phân.

Còn hai việc: tính tọa độ đỉnh sau phép quay, và tính diện tích bóng từ các tọa độ đó.

Quay quanh trục \(x\)

Tọa độ \(x\) không đổi; chỉ \(y,z\) thay đổi. Chiếu \(P=(P_x,P_y,P_z)\) lên mặt phẳng \(yz\) và coi nó là điểm \((P_y,P_z)\). Phép quay theo hướng đã chọn tương đương quay điểm này theo chiều kim đồng hồ một góc \(t\):

Trong ba chiều, điểm mới là \((P_x,P'_y,P'_z)\). Công thức cũng suy ra từ số phức \((P_y+iP_z)e^{-it}\).

Tính diện tích bóng

Khi \(H\) tiến tới trục \(y\), bóng trên \(y=-3\) là một lục giác lồi. Trong ký hiệu của hình chính thức, các đỉnh lục giác là hình chiếu của \(D,C,G,F,E,A\). Hình chiếu của \(P=(P_x,P_y,P_z)\) lên mặt phẳng này là \((P_x,-3,P_z)\).

Ta coi sáu hình chiếu là các điểm hai chiều \((x,z)\). Theo cách dựng, chúng đã là các đỉnh bao lồi theo đúng thứ tự, nên áp dụng trực tiếp công thức diện tích đa giác (dây giày). Với cài đặt tổng quát, có thể dựng convex hull trước; riêng cấu hình này còn có thể tận dụng đối xứng qua trục \(z\) và dùng công thức diện tích hình thang.

Tìm kiếm nhị phân góc cho đến khi diện tích đủ gần \(A\). Khi đã có tư thế, tính tâm của ba mặt đôi một không song song; với ký hiệu đỉnh trong hình chính thức, có thể dùng \(\tfrac12(A+C)\), \(\tfrac12(C+F)\) và \(\tfrac12(F+A)\). Tương đương, áp dụng hai phép quay nói trên cho ba tâm mặt trục ban đầu.

Các cách khác

Phân tích chính thức còn nêu nhiều phương án:

• giải trực tiếp góc thay vì tìm kiếm nhị phân; thậm chí có công thức đóng cho tọa độ cuối mà không cần hàm lượng giác;
• dùng định lý tuyệt đẹp về bóng của khối lập phương để khỏi tính diện tích bằng bao lồi;
• thay hai phép quay quanh \(y\) rồi quanh \(x\) bằng một phép quay quanh đường thẳng nối \((0,0,0)\) với \((1,0,1)\), hoặc một trục tương tự, để đưa một đỉnh lên trục \(y\); khi đó dùng công thức quay tổng quát.

Tìm kiếm nhị phân với số vòng hằng định cho \(O(1)\) thời gian và \(O(1)\) bộ nhớ mỗi test.

Dựa trên phân tích chính thức của Google Code Jam 2018, Vòng loại, bài Cubic UFO.