Mỗi cặp nghệ sĩ là hai đầu mút của một đoạn thẳng. Bài toán yêu cầu tìm các đoạn tham gia ít nhất một cặp không giao nhau, hoặc báo rằng không có cặp như vậy.

Test Set 1 (Visible)

Có thể kiểm tra mọi cặp đoạn. Gọi \(pq\) là đoạn nối \(p,q\) và \(rs\) là đoạn nối \(r,s\). Theo quy ước hướng tích có hướng trong phân tích chính thức, hai đoạn giao nhau khi và chỉ khi:

• \((r-p)\times(q-p)\) cùng dấu với \((s-p)\times(q-p)\); và
• \((p-r)\times(s-r)\) cùng dấu với \((q-r)\times(s-r)\).

Ký hiệu \(\times\) là tích có hướng. Phép kiểm tra này dựa vào giả thiết không có ba điểm thẳng hàng, đúng với bài. Mỗi lần kiểm tra tốn hằng số, nên tổng thời gian là \(O(N^2)\).

Test Set 2 (Hidden)

Gọi \(L_i\) là đường thẳng chứa toàn bộ đoạn \(S_i\). Xét hai đoạn \(S_i,S_j\) không giao nhau. Nếu \(L_i,L_j\) không song song, ít nhất một trong hai đoạn không chứa giao điểm của hai đường. Với mỗi đoạn \(S_i\), ta muốn biết đường \(L_i\) có giao một đường khác ở điểm nằm ngoài \(S_i\) hay không, hoặc hai đường có hoàn toàn không giao nhau hay không.

Gọi \(F\) là tập mọi đoạn có tính chất đó. Mỗi cặp đoạn không giao nhau chứa ít nhất một phần tử của \(F\), và theo bảo đảm của đề, \(|F|\le25\). Sau khi tìm \(F\), với mỗi đoạn trong \(F\) chỉ cần quét tuyến tính qua mọi đoạn khác để tìm cả những đoạn ngoài \(F\) nhưng tham gia một cặp không giao nhau. Phần còn lại tập trung vào cách tìm mọi phần tử của \(F\).

Phân tích chính thức đưa ra ba thuật toán. Hai thuật toán đầu về bản chất tương tự: cách đầu dùng ít lý thuyết nâng cao hơn nhưng phải chứng minh nhiều tính chất riêng của bài. Cả hai cần số nguyên khá lớn. Trong C++, __int128 đủ chứa từng giá trị, nhưng vì phải so sánh các phân số là tỷ số của hai số __int128, cần mã so sánh riêng. Trong Java, BigInteger là đủ. Thuật toán thứ ba dùng một cấu trúc dữ liệu nâng cao hơn nhưng chỉ cần số nguyên 64 bit.

Cách 1: ít kiến thức nâng cao hơn

Trước hết xử lý đoạn thẳng đứng, tức hai đầu có cùng hoành độ. Nếu có hơn một đoạn như vậy, thêm tất cả vào \(F\) vì chúng không chồng lên nhau. Nếu chỉ có một, kiểm tra nó với mọi đoạn còn lại trong thời gian tuyến tính. Sau đây giả sử không có đoạn thẳng đứng.

Kéo dài mỗi \(S_i\) thành đường \(L_i\). Với mỗi \(L_i\), tìm hoành độ giao điểm trái nhất và phải nhất với mọi \(L_j\), rồi kiểm tra chúng có nằm trong khoảng hoành độ mà đoạn \(S_i\) tồn tại hay không. Nếu một giao điểm nằm ngoài khoảng, ta tìm được một hoặc hai đoạn để đưa vào \(F\).

Tìm mọi giao điểm phải nhất tương đương tìm giao điểm trái nhất sau khi phản xạ đầu vào qua trục tung, nên chỉ cần xây dựng thuật toán cho phía trái rồi chạy hai lần. Tiếp tục, chỉ xét giao điểm trái nhất của \(L_i\) với một đường nằm dưới \(L_i\) về phía trái giao điểm; gọi đó là “giao điểm trái nhất từ phía trên”. Chạy thuật toán một lần trên đầu vào gốc và một lần sau khi phản xạ qua trục hoành sẽ tìm thêm trường hợp tương tự “từ phía dưới”. Tổng cộng chạy bốn lần với mọi tổ hợp có/không phản xạ qua mỗi trục để bao phủ giao điểm trái/phải và từ dưới/trên.

Quan sát then chốt: nếu \(L_1,L_2\) giao tại hoành độ \(X\) và \(L_2\) nằm dưới về phía trái giao điểm, thì \(L_2\) không thể tham gia một giao điểm trái nhất kiểu tương ứng nào tại \(X'>X\). Các giao điểm của chính \(L_2\) ở \(X'>X\) không còn là trái nhất. Nếu \(L_2\) giao \(L_3\), với \(L_3\) nằm dưới \(L_2\) về phía trái giao điểm \(X'>X\), thì do tính liên tục và vì \(L_1\) nằm dưới \(L_2\) về phía phải \(X\), \(L_3\) đã giao \(L_1\) ở bên trái \(X'\).

Từ đó có thuật toán ngăn xếp. Gọi \(X_0\) là hoành độ nhỏ nhất trong mọi đầu mút. Sắp các đường theo tung độ tại \(X_0\); gọi \(L_i\) là đường cao thứ \(i\). Duyệt theo thứ tự này, đồng thời duy trì các khoảng hoành độ và đường đã gặp nằm dưới tất cả các đường khác trong từng khoảng — chỉ đường đó mới tạo được giao điểm trái nhất cần tìm. Danh sách được lưu bằng một ngăn xếp.

Ban đầu đẩy \((X_1,1)\), với \(X_1\) là hoành độ lớn nhất trong mọi điểm đầu vào; nghĩa là \(L_1\) đang ở dưới trên toàn bộ khoảng hoành độ. Sau đó lần lượt xử lý \(L_2,L_3,\ldots,L_N\).

Khi xử lý \(L_i\), gọi \((j,X')\) là đỉnh ngăn xếp và tính hoành độ \(X\) của giao điểm \(L_i,L_j\). Kiểm tra giao điểm có thuộc khoảng hoành độ của hai đoạn tương ứng không. Nếu \(X<X'\), chỉ việc đẩy \((i,X)\). Nếu không, lấy \((j,X')\) ra và lặp lại vì \(L_j\) không phải đường thấp nhất tại \(X\). Ngăn xếp luôn tăng theo chỉ số đường và giảm theo hoành độ giao điểm.

Mỗi đường được xử lý, đẩy và lấy ra nhiều nhất một lần; mọi việc khác là hằng số nên lượt duyệt tốn tuyến tính. Sắp theo tung độ tốn \(O(N\log N)\) và chi phối toàn bộ, nên thuật toán có độ phức tạp \(O(N\log N)\).

Cách dùng ngăn xếp rất giống thuật toán bao lồi quen thuộc; phần tiếp theo cho thấy đó không phải ngẫu nhiên.

Cách 2: dùng đối ngẫu điểm–đường

Cách này thay cách tìm các giao điểm trái nhất. Việc xử lý đường thẳng đứng, phản xạ để tìm giao điểm phải nhất, và dùng các cực trị trái/phải để giải bài đều giống cách trên.

Trong phép đối ngẫu, đường \(y=mx+b\) ở không gian gốc được biểu diễn bởi điểm \((m,-b)\) trong không gian đối ngẫu; điểm \((a,b)\) ở không gian gốc được biểu diễn bởi đường \(y=ax-b\) trong không gian đối ngẫu. Đối ngẫu hai lần trở về không gian gốc; đường thẳng đứng không có điểm đối ngẫu.

Khi hai đường \(L_1,L_2\) giao tại điểm \(P\) trong không gian gốc, đường đối ngẫu của \(P\) đi qua hai điểm đối ngẫu của \(L_1,L_2\). Vì vậy, với các điểm đối ngẫu của mọi đường kéo dài từ đoạn đầu vào, giao điểm trái nhất của \(L_1\) là giao với \(L_2\) sao cho hệ số góc đoạn nối \(\operatorname{dual}(L_1)\) và \(\operatorname{dual}(L_2)\) nhỏ nhất.

Bài toán trong không gian đối ngẫu trở thành: với mỗi điểm \(P\), tìm điểm \(Q\) sao cho hệ số góc \(PQ\) nhỏ nhất. Nếu \(P\) thuộc bao lồi, hệ số góc nhỏ nhất đạt với điểm kế tiếp trên bao lồi. Nếu \(P\) nằm trong, lựa chọn đúng là điểm “kế tiếp” tạm thời của bao lồi trong quá trình Graham scan.

Do đó mã nguồn gần giống cách ngăn xếp, nhưng đối ngẫu giúp tránh nhiều chứng minh thủ công. Mọi bước đều tuyến tính ngoại trừ bước sắp xếp của Graham scan, nên tổng thời gian vẫn là \(O(N\log N)\).

Cách 3: bao lồi tăng dần

Cách cuối cần nhiều mã hơn, nhưng một phần có thể đã có trong thư viện hình học. Nó dùng bao lồi tăng dần, cấu trúc duy trì bao lồi của một tập điểm và cho phép thêm điểm, cập nhật bao trong thời gian logarit.

Thuật toán kiểm tra điều kiện đã nêu trong phân tích Part 1: đối với mỗi đoạn, hai đầu mút của mọi đoạn khác phải nằm ở hai phía khác nhau.

Dùng một đường quét quay. Nếu cần, đổi hai đầu mỗi đoạn để đoạn hướng sang phải, tức hoành độ đầu thứ nhất không lớn hơn đầu thứ hai. Sắp các đoạn theo hệ số góc và cho đường quét quay dừng tại từng hệ số góc. Đánh số thứ tự đó là \(S_1,S_2,\ldots,S_N\).

Đối với \(S_1\), mọi đầu trái phải ở một phía và mọi đầu phải ở phía kia. Đối với \(S_2\), điều tương tự đúng, ngoại trừ đầu trái của \(S_1\) đi cùng nhóm các đầu phải còn lại và ngược lại. Tổng quát, khi xét \(S_i\), các đầu trái của \(S_1,\ldots,S_{i-1}\) phải cùng một phía với các đầu phải của \(S_{i+1},\ldots,S_N\); mọi đầu mút còn lại ở phía kia. Nếu đầu mút của \(S_j\) nằm sai phía so với \(S_i\), hai đoạn \(S_i,S_j\) không giao. Nếu không có ví dụ nào, đáp án là MAGNIFICENT.

Nếu biết bao lồi của toàn bộ tập điểm phải nằm ở mỗi phía, có thể tìm kiếm tam phân trên khoảng cách có dấu từ bao lồi đến đường thẳng để tìm hiệu quả điểm có khoảng cách vuông góc nhỏ nhất ở phía phải dương, hoặc lớn nhất ở phía còn lại. Nếu điểm cực trị vẫn đúng phía thì mọi điểm khác cũng đúng; nếu không, ta tìm được vi phạm.

Khó khăn là khi đường quét quay, để duy trì hai bao lồi đầy đủ phải vừa thêm vừa xóa điểm; xóa khó hơn nhiều. Ta tránh việc đó bằng cách, tại hệ số góc của \(S_i\), tách bao lồi một phía thành bao của các đầu trái ở phía đó và bao của các đầu phải ở phía đó. Mỗi phía có thêm một ứng viên cần kiểm tra, nhưng một trong các cực trị này chắc chắn tối ưu.

Do tách đầu trái/phải, \(4(N-1)\) bao lồi cần dùng là: bao của đầu trái trong các tiền tố danh sách đoạn, bao của đầu trái trong các hậu tố, và tương tự cho đầu phải trong tiền tố hoặc hậu tố. Ta tính chúng bằng cấu trúc chỉ hỗ trợ thêm điểm: tính tiền tố theo thứ tự chỉ số tăng, hậu tố theo thứ tự giảm. Như vậy thứ tự xây các bao khác với thứ tự sử dụng trong thuật toán gốc.

Có \(O(N)\) phép chèn và \(O(N)\) lần tìm kiếm tam phân, mỗi phép \(O(\log N)\), nên tổng thời gian \(O(N\log N)\).

Trong ứng dụng này chỉ cần một nửa bao lồi — nửa gần đường đang xét. Các điểm trên nửa bao được sắp theo tung độ, nên tìm trên cây cho vị trí chèn dự kiến rồi duy trì bao bằng tìm kiếm và chèn trong cây có thứ tự. Cấu trúc đủ đơn giản để không nhất thiết cần mã thư viện có sẵn. Ngoài ra, có thể đơn giản hóa thêm bằng tìm kiếm nhị phân theo góc giữa bao lồi và đường thẳng thay cho tìm kiếm tam phân.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2019, Chung kết thế giới, bài Juggle Struggle: Part 2; kho Google Coding Competitions (Apache-2.0).