\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{#008b8b}{\text{Hướng dẫn}}\)

• Để tính diện tích bị che phủ bởi 3 hình chữ nhật \(S_1, S_2, S_3\) ta dùng bao hàm loại trừ

Gọi hình chữ nhật \(S\) tương ứng giá trị trừu tượng \(Rect(x_S, y_S, u_S, v_S)\) nghĩa là \(S\) có tọa độ trái dưới \((x_S, y_S)\), phải trên \((u_S, v_S)\)

Gọi hình chữ nhật \(S\) tương ứng giá trị trừu tượng \(Rect(w_S, h_S)\) là hình chữ nhật có chiều dài \(w_S = u_S - x_S + 1\) và chiều cao \(h_S = v_S - y_S + 1\)

Trong trường hợp . \((x_S \geq u_S)\) hoặc \((y_S \geq v_S)\) thì coi như hình chữ nhật này rỗng và \(|S| = 0\). Ngược lại ta có diện tích \(|S| = w_S \times h_S = (y_S - x_S + 1) \times (v_S - u_S + 1)\)

Hợp hai hình chữ nhật \(S\) và \(T\) là \(S \cap T = Rect(x_S, y_S, u_S, v_S) \cap Rect(x_T, y_T, u_T, v_T) = Rect\Big(\ max(x_S, x_T)\ ,\ max(y_S, y_T)\ ,\ min(u_S, u_T)\ ,\ min(v_S, v_T)\ \Big)\)

Ta có \(|S_1 \cup S_2 \cup S_3| = |S_1| + |S_2| + |S_3| - |S_1 \cap S_2| - |S_2 \cap S_3| - |S_3 \cap S_1| + |S_1 \cap S_2 \cap S_3|\)

• Nhận xét rằng: Xét các hình chữ nhật cố định và không quay, khi cho tất cả các hình chữ nhật đều có chung ô góc (trái dưới, phải dưới, trái trên, phải trên) thì diện tịch bị che phủ là nhỏ nhật

Xét một tập các hình chữ nhật là \(T (= T_1 \cap T_2 \cap \dots \cap T_n)\) và hinh chữ nhật đang xét là \(S\)

Thì có \(|T \cup S| = |T| + |S| - |T \cap S|\), mà \(|T|\) và \(|S|\) là hằng số nên phần chung \((T \cap S)\) có diện tích càng lớn thì tổng số ô bị chiếm càng giảm

Ta cần chứng minh khi mà các hình chữ nhật chia chung ô góc thì diên tích che phủ là bé nhất

Không mất tính tổng quát xét hai hình chữ nhật \(A, B\) và kiểm tra ô góc trái dưới

Ta có \(max\Big(\ \Big|A \cap B\Big|\ \Big) = max\Big(\ \Big|\ Rect(x_A, y_A, u_A, v_A) \cap Rect(x_B, y_B, u_B, v_B)\ \Big|\ \Big)\)

\(= max\Big(\ \Big|\ Rect\Big(\ max(x_A, x_B)\ ,\ max(y_A, y_B)\ ,\ min(u_A, u_B)\ ,\ min(v_A, v_B)\ \Big)\ \Big| \ \Big)\)

\(= max\Big(min(u_A, u_B) - max(x_A, x_B)\Big) \times max\Big(min(v_A, v_B) - max(y_A, y_B)\Big)\)

Không mất tính tổng quát giả sử đã biết \(2\) giá trị \(w_A, w_B\) và \(w_A \geq w_B\).

Không mất tính tổng quát coi \(A\) cố định và chỉ được tịnh tiến hình \(B\)

Ta có \(max\Big(min(u_A, u_B) - max(x_A, x_B)\Big) = max\Big( min(u_A, u_B) - max(x_A, x_B) \ \ \Big|\ \ const(w_A)\ \land\ const(x_A)\ \land\ x_B \in \mathbb{Z}) = w_B\) khi và chỉ khi \(x_A \leq x_B < u_B \leq u_A\)

Từ trên \(\Rightarrow max\Big(min(u_A, u_B) - max(x_A, x_B)\Big) = min(w_A, w_B)\) và xảy ra khi và chỉ khi \(\Big((x_A \leq x_B < u_B \leq u_A)\ \Large \lor \normalsize (x_B \leq x_A < u_A \leq u_B)\Big)\)

Tương tự \(\Rightarrow max\Big(min(v_A, v_B) - max(y_A, y_B)\Big) = min(h_A, h_B)\) và xảy ra khi và chỉ khi \(\Big((y_A \leq y_B < v_B \leq v_A)\ \Large \lor \normalsize (y_B \leq y_A < v_A \leq v_B)\Big)\)

Vậy \(max\Big(\ \Big|A \cap B\Big|\ \Big) = min(w_A, w_B) \times min(h_A, h_B)\) xảy ra khi và chỉ khi \(\Big((x_A \leq x_B < u_B \leq u_A)\ \Large \lor \normalsize (x_B \leq x_A < u_A \leq u_B)\Big) \LARGE\land \normalsize \Big((y_A \leq y_B < v_B \leq v_A)\ \Large \lor \normalsize (y_B \leq y_A < v_A \leq v_B)\Big)\).

Mà hai hình chữ nhật có chung góc thì thỏa điều kiện trên \(\Rightarrow\) (đpcm)

Tương tự ta chứng minh với \(n\) hình chữ nhật, cũng thỏa tính chất này (trong bài này \(n = 3\))

• Lưu ý rằng hình chữ nhật \(S_x = a_x \times b_x\) thì \(a_x\) có thể là chiều dài hoặc rộng, nên ta sẽ phải quay hình, và trong các cách quay ta chọn cách có diện tích che phủ nhỏ nhất

\(\color{#008b8b}{\text{Tiếp cận}}\)

• Ta có thể duyệt qua bitmask để quay:

Bit thứ \(ith\) là \(0\) thì dài \(b_i\) rộng \(a_i\)

Bit thứ \(ith\) là \(1\) thì dài \(a_i\) rộng \(b_i\)

• Để tính giá trị hình chữ nhật:

Hình chữ nhật \(S_x\) tại gốc tọa độ có chiều dài \(a_x\) và chiều rộng \(b_x\) \(\Rightarrow S = Rect(0, 0, a_x, b_x)\)

Thì ta có \(S_1 \cap S_2 \cap \dots \cap S_n = Rect(0, 0, a_1, b_1) \cap Rect(0, 0, a_2, b_2) \cap \dots \cap Rect(0, 0, a_, b_n) = min(a_1, a_2, \dots, a_n) \times min(b_1, b_2, \dots, b_n)\)

Từ đó ta có thể dùng bao hàm loại trừ tính \(S_1 \cup S_2 \cup \dots \cup S_n\)

\(\color{#008b8b}{\text{Độ phức tạp}}\)

• Số cách quay cho một hình chữ nhật là \(2\). Nên \(n\) hình chữ nhật sẽ có \(2^n\) cách quay

• Số giá trị cần tính trong bao hàm loại trừ là \(C^1_n + C^2_n + \dots + C^{n-1}_n = 2^n - 1\)

• Gọi \(Q\) là số truy vấn thì ta cần \(O(Q \times 2^n \times 2^n)\) thời gian và \(O(n)\) bộ nhớ

\(\color{#008b8b}{\text{Tối ưu tính toán}}\)

• Trong trương hợp số hình chữ nhật lớn hơn, sau khi thử các phép quay, ta có thể sắp xếp theo chiều \(x\).

• Trong những hình chữ nhật có cùng độ dài \(x\) ta chọn \(y\) có độ dài cao nhất, từ đó ta có hợp của các hình chữ nhật là hình thang và tính trong \(O(n\ log\ n)\)

• Ta cũng không cần quay các hình vuông, vì nó như nhau.

• Vậy độ phức tạp rút xuống còn \(o(2^n) \times O(n\ log\ n)\)

\(\color{#008b8b}{\text{Code tham khảo }}\): Cài đặt

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(Q \times 2^{2n})\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

#define min3(a, b, c) min(a, min(b, c))
int main()
{
    int a[3], b[3];
    while (true)
    {
        cin >> a[0] >> b[0] >> a[1] >> b[1] >> a[2] >> b[2];
        if ((a[0] | b[0] | a[1] | b[1] | a[2] | b[2]) == 0) break;

        int res = 1e9;
        for (int mask = 0; mask < 8; ++mask)
        {
            int x[3], y[3];
            for (int i = 0; i < 3; ++i)
            {
                x[i] = (mask >> i & 1) ? a[i] : b[i];
                y[i] = (mask >> i & 1) ? b[i] : a[i];
            }

            int SA = x[0] * y[0];
            int SB = x[1] * y[1];
            int SC = x[2] * y[2];
            int SAB = min(x[0], x[1]) * min(y[0], y[1]);
            int SBC = min(x[1], x[2]) * min(y[1], y[2]);
            int SCA = min(x[2], x[0]) * min(y[2], y[0]);
            int SABC = min3(x[0], x[1], x[2]) * min3(y[0], y[1], y[2]);
            int val = SA + SB + SC - SAB - SBC - SCA + SABC;
            res = min(res, val);
        }

        cout << res << '\n'; 
    }

    return 0;
}