Người viết:Reviewer:Một số bài toán trung bình khó yêu cầu người giải phải thực hiện thao tác ghép hai bao lồi như sau: với hai bao lồi AAA và BBB, dựng một đa giác CCC chỉ bao gồm các điểm a+ba + ba+b với a∈Aa \in Aa∈A và b∈Bb \in Bb∈B (ở đây một điểm thuộc bao lồi nếu nó nằm trong/trên bao lồi, và việc cộng điểm được thực hiện như việc cộng véctơ). Đây chính là việc tìm tổng Minkowski của hai bao lồi AAA và BBB.Ở bài viết sau, chúng ta hãy cùng xem qua cách tìm tổng Minkowski một cách hiệu quả, cũng như một số bài toán có thể được giải thông qua thuật toán này.Bài viết này là phần 2 của chuỗi bài viết về các kĩ thuật xử lí bao lồi/hàm lồi; các bạn có thể đọc phần 1 ở đây. Một phần của bài viết được tham khảo từ cp-algorithm. Template code hình được lấy từ kactl.Để nhắc lại từ phần giới thiệu, ta định nghĩa tổng Minkowski A+BA + BA+B của hai bao lồi AAA và BBB như sau:Như ta thấy ở ví dụ trên, A+BA + BA+B cũng là một bao lồi và có số lượng điểm là 555. Một cách tổng quát hơn, ta có thể chứng minh được là tổng A+BA + BA+B cũng là đa giác lồi và có tối đa ∣A∣+∣B∣

∣A∣+∣B∣ đỉnh.Lấy ví dụ vừa nêu trên, ta có thể nhìn A+BA + BA+B dưới một góc nhìn khác như sau.Ta có hai nhận xét sau:Vì thế ta có thể dựng A+BA + BA+B như sau (giả sử rằng AAA và BBB đi ngược chiều kim đồng hồ và được xoay lại sao cho A1A_1A1 và B1B_1B1 là đỉnh trái dưới của AAA và BBB):Ta có thể coi thuật toán này như việc sắp xếp cạnh của hai bao lồi AAA và BBB : do cạnh của AAA và BBB đã được sắp xếp sẵn ngược chiều kim đồng hồ, ta chỉ cần chạy thuật toán ghép hai mảng đã được sắp xếp giống như bước ghép trong merge sort.Dưới đây là một cách cài đặt mẫu:Độ phức tạp của thuật toán là O(∣A∣+∣B∣)O(

)O(∣A∣+∣B∣).Link bài: CF 87E.Cho ba bao lồi AAA, BBB và CCC và qqq truy vấn. Với mỗi truy vấn, ta được nhận một điểm xxx, và ta cần trả lời rằng có tồn tại ba điểm a∈Aa \in Aa∈A, b∈Bb \in Bb∈B, và c∈Cc \in Cc∈C sao cho điểm xxx là trọng tâm của tam giác được tạo bởi a,b,ca, b, ca,b,c (1≤∣A∣,∣B∣,∣C∣,q≤1051 \le

, q \le 10^51≤∣A∣,∣B∣,∣C∣,q≤105).Nhận xét rằng xxx là trọng tâm của tam giác tạo bởi a,b,ca, b, ca,b,c khi và chỉ khi 3x=a+b+c3x = a + b + c3x=a+b+c. Nói cách khác, điểm 3x3x3x phải thuộc tổng Minkowski A+B+CA + B + CA+B+C. Vì thế, ta chỉ cần dựng trước A+B+CA + B + CA+B+C, và với mỗi truy vấn ta chỉ cần kiểm tra nếu điểm 3x3x3x thuộc bao lồi này không là được.Các bạn có thể tham khảo cách cài đặt tại đây. Ở phần cài đặt này, hàm minkowskiSum nhận một tập các bao lồi (không nhất thiết chỉ là 2 bao lồi) và trả về tổng Minkowski của tập bao lồi này. Độ phức tạp là O(p+qlog⁡p)O(p + q \log p)O(p+qlogp), với p≤∣A∣+∣B∣+∣C∣p \le

p≤∣A∣+∣B∣+∣C∣ là số lượng điểm trong tổng Minkowski.Cho hai bao lồi AAA và BBB, tìm khoảng cách ngắn nhất giữa hai điểm bất kì thuộc hai bao lồi này. Nếu AAA và BBB có điểm chung thì in ra 0 (1≤∣A∣,∣B∣≤2⋅1051 \le

\le 2 \cdot 10^51≤∣A∣,∣B∣≤2⋅105).Đây là một bài toán kinh điển sử dụng tổng Minkowski. Nhận xét là bài toán có thể được viết như sau (ở đây ∣∣u∣∣2=xu2+yu2

2 = \sqrt{x_u^2 + y_u^2}∣∣u∣∣2=xu2+yu2 là khoảng cách của uuu tới gốc tọa độ):min⁡a∈A,b∈B∣∣a−b∣∣2=min⁡a∈A,b∈B∣∣a+(−b)∣∣2\min{a \in A, b \in B}

a - b

2 = \min{a \in A, b \in B}

a + (-b)

a∈A,b∈Bmin∣∣a−b∣∣2=a∈A,b∈Bmin∣∣a+(−b)∣∣2Vì thế, nếu ta gọi −B-B−B chứa tất cả các điểm −b-b−b khi b∈Bb \in Bb∈B thì bài toán tương đương với việc tìm min⁡a∈A,c∈−B∣∣a+c∣∣2\min_{a \in A, c \in -B}

a + c

_2mina∈A,c∈−B∣∣a+c∣∣2. Gọi S=A+(−B)S = A + (-B)S=A+(−B) là tổng Minkowski của bao lồi AAA và −B-B−B, thì bài toán trở thành: tìm điểm trong SSS gần gốc tọa độ nhất. Bài toán này ta có thể giải một cách dễ dàng: nếu SSS chứa gốc tọa độ thì đáp án là 000, ngược lại thì ta có thể lặp qua cạnh của SSS và tìm khoảng cách ngắn nhất từ gốc tọa độ tới từng cạnh của SSS.Các bạn có thể tham khảo cách cài đặt dưới đây.Độ phức tạp của thuật toán là O(n+m)O(n + m)O(n+m).