Phân tích

Nếu ta chỉ giới hạn hướng tô màu là trái/phải, thì sẽ luôn tồn tại một hình chữ nhật màu trắng có chu vi ít nhất là \(2H+2\).
Tương tự, nếu chỉ giới hạn hướng tô là trên/dưới, thì chu vi đạt được ít nhất là \(2W+2\).
Từ đó, có thể khẳng định rằng trong phương án tối ưu, hình chữ nhật trắng còn lại chắc chắn sẽ cắt qua ít nhất một trong hai đường \(x=W/2\) hoặc \(y=H/2\).
Do đó, ta chỉ cần xét các hình chữ nhật cắt qua đường thẳng \(x=x_c\) nào đó (ví dụ \(x=W/2\)). Sau đó xoay các điểm 90° và lặp lại giải pháp.
Với giả định này, bài toán có thể được giải bằng phương pháp Chia để trị.

Chia

Khi chỉ xét các hình chữ nhật cắt qua đường \(x=x_c\), ta tiến hành:

• Chia \(N\) điểm theo giá trị \(y\) thành hai phần: các điểm có \(y≤y_c\) và các điểm có \(y>y_c\).
• Cách chia này là hợp lệ vì không có hai điểm nào trùng hoành độ hay tung độ.
• Gọi phần dưới là "nửa dưới", phần trên là "nửa trên".

Trị

Ta sẽ đệ quy để giải cho hai phần nửa dưới và nửa trên, tức là xem như bài toán con gồm các hình chữ nhật giao với đường \(x=x_c\) và nằm hoàn toàn phía dưới hoặc phía trên \(y_c\).

Kết hợp

Còn lại là phần giao nhau tại đúng điểm \((xc, yc)\). Phần này gọi là phần chính.
Giả sử ta xét các điểm có \(x≤x_c\) (bên trái đường \(x=x_c\)).
Giả định rằng \(x=t\) là cạnh trái của hình chữ nhật trắng còn lại.

• Với các điểm có \(x≤t →\) ta tô phần bên trái → không ảnh hưởng gì đến phần chứa (\(x_c,y_c\))
• Với các điểm có \(x>t →\) vì không thể tô (\(x_c,y_c\) ), nên phải chọn hướng tô là trên hoặc dưới, và hướng này là duy nhất để không chạm vào đường \(y=y_c\).

Kết quả là, khi ta chọn t làm cạnh trái, vùng trắng còn lại sẽ có giới hạn y nằm trong khoảng \([lt,ut]\).
Nhận xét: \(lt\) và \(ut\) chỉ thay đổi khi x thay đổi, tức là ta chỉ cần xét các \(x\) có điểm xuất hiện.
Với mỗi điểm, ta tính toán nếu lấy \(x=x_i\) làm cạnh trái, thì \(y\) nằm trong miền \([y_1,y_2 ]\) nào.
Lưu lại các bộ \((x_i,[y_1,y_2])\) vào một danh sách \(L\).
Tương tự, ta cũng làm như vậy với các điểm có \(x>x_c\) (bên phải), lưu các bộ \((x_j,[y_3,y_4 ])\) vào một danh sách \(R\).
Với hai danh sách \(L,R\), cần chọn một bộ từ \(L\) và một bộ từ \(R\) sao cho:
Phần giao nhau về \(y\) của hai miền (\([y_1,y_2 ]\) và \([y_3,y_4 ]\)) không rỗng
Tổng chiều rộng \((x_R-x_L\)) + chiều cao (độ dài miền \([y_1,y_2 ]∩[y_3,y_4 ]\)) là lớn nhất, tức là chu vi lớn nhất.
Hầu hết học sinh/thí sinh tham gia nhiều cuộc thi online sẽ sử dụng segment tree để giải quyết bước này.
Nhận xét: Các đoạn \([y_1,y_2 ]\) trong \(L\) và \([y_3,y_4 ]\) trong \(R\) có thể được xây dựng sao cho danh sách có tính chất đơn điệu (tăng hoặc giảm).
Do đó, có thể dùng deque (hàng đợi hai đầu) và trick sliding để giữ các đoạn tốt nhất
Cụ thể, với mỗi đoạn bên trái l∈L, xét các đoạn bên phải \(r∈R\). \(R\) được chia thành 3 nhóm:

• Nhóm A: \(r\) bao phủ \(l\) → dễ chọn đoạn có x lớn nhất
• Nhóm B: \(r\) nằm trong \(l\) → chọn \(r\) có (\(x+\) độ dài đoạn) lớn nhất
• Nhóm C: \(r\) giao nhưng không bao phủ hoặc bị bao phủ → dùng deque để giữ các \(r\) tốt nhất

Deque luôn chỉ giữ lại các \(r\) có khả năng cho chu vi lớn nhất. Khi duyệt qua tất cả \(l\), chỉ cần trượt qua deque để lấy đoạn tốt nhất.
Cách xử lí trên đảm bảo tổng chi phí \(O(N)\) cho phần kết hợp.
Độ phức tạp tính toán: \(O(N log⁡N )\) cho giải pháp Chia để trị sử dụng deque, \(O(N log^2⁡N )\) cho giải pháp Chia để trị dùng segment tree để quản lí các danh sách \(L,R\).