Review in round 7 Câu D
posted on Aug. 4, 2023, 9:09 a.m. 0Tóm tắt đề bài
Bài toán sử dụng kĩ thuật ghép hình rất hay gặp trong các bài Dynamic Programming hình học. Ở cuối bài viết, mình giới thiệu một số bài toán tương tự sử dụng kĩ thuật này.
Cách tiếp cận 1: Duyệt qua tất cả tập con , tìm diện tích bao lồi và cập nhật kết quả. Lưu ý rằng . Độ phức tạp . Với giới hạn , thuật toán trên không tối ưu. Trước khi đến cách tiếp cận tối ưu hơn, ta có một số nhận xét như sau:
Nhận xét 1: Với các đỉnh tọa độ nguyên, diện tích đa giác (kể cả đa giác không lồi) có giá trị nguyên khi và chỉ khi hai lần diện tích đa giác là số chẵn (dễ dàng chứng minh với Pick’s theorem hoặc Shoelace formula).
Nhận xét 2: Với tập điểm , gọi là tập các điểm nằm trên bao lồi của và là tập các điểm nằm bên trong bao lồi của . Gọi là tập con của và là tập các điểm nằm trên bao lồi của . Khi đó số lượng tập thỏa mãn (bao lồi của và trùng nhau) là . Ví dụ: Hình có tập thỏa mãn .
Nhận xét 3: Quan sát ở hình , gọi điểm có hoành độ nhỏ nhất là điểm trái nhất và điểm có hoành độ lớn nhất
là điểm phải nhất . Từ đoạn thẳng nối hai điểm trên, ta có thể chia đa giác lồi thành hai phần:
phần nửa trên (tạm gọi là Upper) gồm các điểm nằm phía trên đường nối và phần nửa dưới (Lower) gồm các điểm nằm phía dưới đường nối.
Khi đó diện tích đa giác lồi bằng tổng diện tích hai phần nửa trên và nửa dưới: Convex_Area = Upper_Area + Lower_Area
.
Cách tiếp cận 2: Quy hoạch động với kĩ thuật ghép hình:
Sắp xếp điểm theo thứ tự tăng dần hoành độ , nếu có cùng hoành độ , sắp xếp theo thứ tự tăng dần tung độ . Duyệt qua với mọi đỉnh , ta đếm số lượng tập điểm thỏa mãn yêu cầu đề bài và bao lồi của nó nhận điểm là điểm trái nhất (có hoành độ nhỏ nhất) với tư tưởng quy hoạch động như sau:
Gọi dp[z][i][j][k]
với là số lượng tập thỏa mãn đồng
thời các yêu cầu sau:
Bao lồi của nó nhận điểm là điểm trái nhất và là điểm phải nhất.
nếu là một Upper (mọi điểm thuộc tập nằm phía trên đường nối và ) và nếu là một Lower (mọi điểm thuộc tập nằm phía dưới đường nối và ).
Bao lồi của nó nhận điểm là điểm liền kề đứng trước điểm (khi duyệt bao lồi từ đến , hai điểm cuối cùng được duyệt tương ứng là và ).
Phần dư khi chia hai lần diện tích bao lồi của cho bằng ( nếu hai lần diện tích là số chẵn và nếu hai lần diện tích là số lẻ).
Cách tính dp[z][i][j][k]
được mình họa ở hình sau:
Tư tưởng ghép hình: Với đa giác lồi đã được tính toán, ta tiến hành ghép tam giác với để có được đa giác mới . Từ đó, ta có công thức quy hoạch động như sau:
Trong đó:
parity[a][b][c] = 0
nếu hai lần diện tích tam giác là số chẵn, ngược lạiparity[a][b][c] = 1
.cnt[a][b][c]
là số lượng điểm nằm bên trong tam giác .nếu điểm theo thứ tự chiều kim đồng hồ và nếu điểm theo thứ tự ngược chiều kim đồng hồ.
Các giá trị parity[a][b][c]
và cnt[a][b][c]
có thể tính toán trước trong .
Một số lưu ý trong công thức QHĐ trên:
Việc ta phải nhân với đã được đề cập trong nhận xét 2.
Giới hạn của là chứ không phải . Việc do Upper hoặc Lower có thể là một đoạn thẳng (đa giác chỉ có đỉnh). Minh họa ở hình:
Từ nhận xét 3, ta có kết quả của bài toán được tính theo công thức:
Lưu ý rằng ở đáp án, ta phải trừ đi số lượng tập với do ta đã đề cập về vấn đề Upper hoặc Lower có thể là một đoạn thẳng ở trên.
Mở rộng: Kĩ thuật ghép hình như trên được dùng ở hầu hết các bài toán QHĐ hình học, đặc biệt là hình học bao lồi. Để luyện tập kĩ thuật này, các bạn có thể tham khảo một số bài toán:
Empty Convex Polygons - vjudge : Bài toán theo mình khá hay vì thể hiện rõ việc sử dụng kĩ thuật “ghép hình” để tìm đa giác lồi rỗng (đa giác không có điểm nằm trong) có diện tích lớn nhất.
Polygon – codeforces : Mặc dù ở mức 3000* nhưng với việc áp dụng kĩ thuật “ghép hình” thì tư tưởng để giải bài toán này không quá khó.
Mã nguồn tham khảo