Khái niệm omnicircumnavigation yêu cầu hành trình chạm mọi bán cầu. Chọn một mặt phẳng \(P\) qua gốc; nó chia mặt cầu thành hai bán cầu mở và đường tròn biên. Nếu toàn bộ đường đi nằm trong một bán cầu mở thì hành trình không phải omnicircumnavigation. Vì vậy bài toán là tìm một mặt phẳng phân chia như vậy hoặc chứng minh không tồn tại.

Đường đi chạm \(P\) khi và chỉ khi có một điểm dừng nằm trên \(P\), hoặc có các điểm dừng ở hai bán cầu khác nhau khiến cung nối chúng đi qua \(P\). Do đó, một định nghĩa tương đương của mặt phẳng phân chia là mặt phẳng đặt mọi điểm dừng nghiêm ngặt trong cùng một bán cầu. Thứ tự các điểm không còn quan trọng: mọi hoán vị hợp lệ của cùng tập điểm cho cùng đáp án.

Điểm dừng thật \(S\) là vectơ chuẩn hóa của điểm nguyên \(S'\) trong input. Gốc, \(S,S'\) thẳng hàng nên mọi mặt phẳng qua gốc đặt \(S\) và \(S'\) ở cùng phía. Ta có thể dùng trực tiếp tọa độ nguyên, vừa tương đương vừa chính xác hơn.

Tóm lại, bài toán trở thành: với tập \(X\) các điểm nguyên, có tồn tại mặt phẳng qua gốc đặt mọi điểm trong \(X\) nghiêm ngặt cùng một phía hay không?

Các lời giải dựa trên bao lồi

Nếu có mặt phẳng phân chia, toàn bộ bao lồi của các điểm cũng nằm cùng phía. Theo tính lồi, mặt phẳng ấy tồn tại khi và chỉ khi bao lồi không chứa gốc. Có thể tính bao lồi của \(X\) cộng thêm gốc rồi kiểm tra gốc có là một đỉnh hay không; cách này thậm chí có thể giải Large.

Tuy nhiên, bao lồi 3D khó cài đặt, và nhiều cài đặt gặp sai số, tràn số hoặc chậm vì số nguyên ngày càng lớn. Mặt phẳng cần tìm có thể rất xiên, với góc cỡ \(10^{-6}\). Nếu toàn bộ input đồng phẳng, thuật toán bao lồi cũng có thể thất bại. Một cách xử lý cả hai là thêm một điểm \(F\) thật xa cùng với gốc; \(F\) phá đồng phẳng và làm bao lồi không có phần quá hẹp. Vì \(F\) có thể khiến bao mới chứa gốc dù bao cũ không chứa, chạy lần hai với điểm đối \(-F\). Nếu bao gốc chứa gốc, cả hai lần vẫn chứa. Nếu không, ít nhất một trong \(F,-F\) nằm về phía thích hợp của mặt phẳng phân chia, nên một lần vẫn không chứa gốc.

Một cách đơn giản hóa là dùng việc mọi đa diện đều có thể được chia thành các tứ diện, tương tự tam giác hóa đa giác lồi. Ta không cần dựng bao lồi tường minh nếu kiểm tra mọi tứ diện. Không có dương tính giả vì mỗi tứ diện nằm trong bao lồi; ngược lại, một số tứ diện phân hoạch toàn bộ bao lồi, nên nếu bao chứa gốc thì một tứ diện chứa gốc. Vậy bao lồi của \(X\) chứa gốc khi và chỉ khi có một tứ diện với đỉnh trong \(X\) chứa gốc.

Nếu toàn bộ input đồng phẳng, chỉ cần kiểm tra tam giác chứa gốc; cũng có thể tránh trường hợp riêng bằng các điểm ma \(F,-F\). Thử mọi tứ diện tốn \(O(N^4)\), chắc chắn quá chậm cho Large và có thể cả Small vì mỗi phép kiểm tra cần nhiều phép nhân dù chỉ là hằng số.

Để đủ nhanh cho Small, cố định một đỉnh \(V\) và thử mọi bộ ba đỉnh còn lại. Với bất kỳ \(V\), tồn tại một phép chia tứ diện của bao lồi mà mọi tứ diện đều có \(V\) làm đỉnh. Độ phức tạp giảm còn \(O(N^3)\), đủ cho Small dù hằng số lớn.

Hạn chế các mặt phẳng phân chia

Như thường thấy trong hình học, có thể giảm vô số ứng viên xuống hữu hạn. Giả sử có mặt phẳng phân chia \(P\). Xoay \(P\) quanh gốc tới khi nó chạm một điểm input \(S\), rồi xoay quanh đường thẳng \(OS\) tới khi chạm điểm thứ hai. Do đó chỉ cần xét các mặt phẳng qua gốc và hai điểm input, tổng cộng \(O(N^2)\) ứng viên. Quét mọi điểm để kiểm tra phía tạo thuật toán \(O(N^3)\), đủ cho Small nhưng hằng số khiến Large vẫn quá chậm.

Mặt phẳng ứng viên chạm các điểm nên bản thân nó chưa phải mặt phẳng phân chia; nó đại diện cho mặt phẳng cách một góc \(\varepsilon\). Phải cẩn thận với bất đẳng thức để một phép xoay nhỏ không phá lời giải. Nếu có điểm thứ ba cùng nằm trên mặt phẳng, không nhất thiết xoay được sao cho cả ba về cùng phía. Cần xử lý trường hợp đồng phẳng bằng bài toán 2D hoặc điểm ma.

Có thể tăng tốc bằng cách xáo trộn input, tức thứ tự kiểm tra điểm. Với phần lớn mặt phẳng, nhiều điểm nằm ở mỗi phía; trong thứ tự ngẫu nhiên, kỳ vọng sớm gặp một điểm ở mỗi phía và dừng. Nếu toàn bộ điểm đồng phẳng, ngẫu nhiên hóa không cải thiện vì không điểm nào nằm nghiêm ngặt ở một phía. Vì vậy phải phát hiện và xử lý riêng ca toàn đồng phẳng trước khi chạy thuật toán tổng quát. Phiên bản ngẫu nhiên đủ nhanh cho Large.

Dùng “bazooka để diệt ruồi”: lập trình tuyến tính

Mặt phẳng qua gốc có phương trình \(Ax+By+Cz=0\). Nó đặt mọi điểm cùng phía nếu với mọi \((X,Y,Z)\) ta có

hoặc tất cả đều nhỏ hơn 0. Nếu \((A,B,C)\) thỏa trường hợp đầu thì \((-A,-B,-C)\) thỏa trường hợp sau, nên chỉ cần xét một trường hợp. Các bất đẳng thức tạo thành một miền đa diện; đáp án phụ thuộc miền này có rỗng hay không. Nhiều thuật toán LP xác định điều đó trong quá trình tối ưu; nếu thư viện không có thao tác trực tiếp, tối ưu hàm hằng 0 và xem kết quả là 0 hay “không có nghiệm”.

Mô tả ngắn nhưng có nhiều vấn đề thực tế. Thư viện dễ gặp cùng lỗi sai số và số lớn như bao lồi, khiến lời giải sai, chậm hoặc cả hai. Tự cài một thuật toán tránh sai số thì dài và cồng kềnh. Có thể bắt trường hợp đáng ngờ rồi xoay input, hoặc thêm ràng buộc \(|A|,|B|,|C|\le10^6\) để miền bị chặn. Nhóm ra đề thử bốn thư viện LP và chỉ một thư viện hoạt động sau khi vừa thêm các ràng buộc — thư viện không xử lý miền không bị chặn — vừa xoay input vài lần. Điểm ma thật xa cũng giúp tránh vấn đề giống bao lồi. Nếu có sẵn thuật toán hoặc thư viện rất vững, đây lại là lựa chọn tốt nhất, thậm chí có thể cho lời giải ba dòng qua cả Small lẫn Large.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2017, Chung kết thế giới.