Review in round 7 Câu D

Yunan posted on Aug. 4, 2023, 4:09 p.m.

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 $S$ ~S~, tìm diện tích bao lồi và cập nhật kết quả. Lưu ý rằng $|S| \geq 3$ ~|S| \geq 3~. Độ phức tạp $\mathcal{O}(2^n.nlogn)$ ~\mathcal{O}(2^n.nlogn)~. Với giới hạn $n \le 80$ ~n \le 80~, 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 $S$ ~S~, gọi $S_{on}$ ~S_{on}~ là tập các điểm nằm trên bao lồi của $S$ ~S~ và $S_{in}$ ~S_{in}~ là tập các điểm nằm bên trong bao lồi của $S (S_{on} \cup S_{in} = S)$ ~S (S_{on} \cup S_{in} = S)~. Gọi $S'$ ~S'~ là tập con của $S$ ~S~ và $S'_{on}$ ~S'_{on}~ là tập các điểm nằm trên bao lồi của $S'$ ~S'~. Khi đó số lượng tập $S'$ ~S'~ thỏa mãn $S_{on} = S'_{on}$ ~S_{on} = S'_{on}~ (bao lồi của $S$ ~S~ và $S'$ ~S'~ trùng nhau) là $2^{|S_{in}|}$ ~2^{|S_{in}|}~. Ví dụ: Hình $1$ ~1~ có $2^4 = 16$ ~2^4 = 16~ tập $S'$ ~S'~ thỏa mãn $S_{on} = S'_{on}$ ~S_{on} = S'_{on}~.

Nhận xét 3: Quan sát ở hình $2$ ~2~, gọi điểm có hoành độ $x$ ~x~ nhỏ nhất là điểm trái nhất $P_{left}$ ~P_{left}~ và điểm có hoành độ $x$ ~x~ lớn nhất là điểm phải nhất $P_{right}$ ~P_{right}~. 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 $n$ ~n~ điểm theo thứ tự tăng dần hoành độ $x$ ~x~, nếu có cùng hoành độ $x$ ~x~, sắp xếp theo thứ tự tăng dần tung độ $y$ ~y~. Duyệt qua với mọi đỉnh $P_{left}$ ~P_{left}~, ta đếm số lượng tập điểm $S$ ~S~ thỏa mãn yêu cầu đề bài và bao lồi của nó nhận điểm $P_{left}$ ~P_{left}~ là điểm trái nhất (có hoành độ $x$ ~x~ nhỏ nhất) với tư tưởng quy hoạch động như sau:

Gọi dp[z][i][j][k] với $0 \le z \le 1,left < j \le n,left \le i < j,0 \le k \le 1$ là số lượng tập $S$ ~S~ thỏa mãn đồng thời các yêu cầu sau:

Bao lồi của nó nhận điểm $P_{left}$ ~P_{left}~ là điểm trái nhất và $P_j$ ~P_j~ là điểm phải nhất.
$z=0$ ~z=0~ nếu $S$ ~S~ là một Upper (mọi điểm thuộc tập $S$ ~S~ nằm phía trên đường nối $P_{left}$ ~P_{left}~ và $P_j$ ~P_j~) và $z=1$ ~z=1~ nếu $S$ ~S~ là một Lower (mọi điểm thuộc tập $S$ ~S~ nằm phía dưới đường nối $P_{left}$ ~P_{left}~ và $P_j$ ~P_j~).
Bao lồi của nó nhận điểm $P_i$ ~P_i~ là điểm liền kề đứng trước điểm $P_j$ ~P_j~ (khi duyệt bao lồi từ $P_{left}$ ~P_{left}~ đến $P_j$ ~P_j~, hai điểm cuối cùng được duyệt tương ứng là $P_i$ ~P_i~ và $P_j$ ~P_j~).
Phần dư khi chia hai lần diện tích bao lồi của $S$ ~S~ cho $2$ ~2~ bằng $k$ ~k~ ( $k = 0$ ~k = 0~ nếu hai lần diện tích là số chẵn và $k = 1$ ~k = 1~ 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 ở $2$ ~2~ hình sau:

Tư tưởng ghép hình: Với đa giác lồi $\{P_{left},\ldots, P_i,P_j\}$ ~\{P_{left},\ldots, P_i,P_j\}~ đã được tính toán, ta tiến hành ghép tam giác $\{P_{left}, P_j, P_l\}$ ~\{P_{left}, P_j, P_l\}~ với $(j <l)$ ~(j <l)~ để có được đa giác mới $\{P_{left},\ldots, P_j,P_l\}$ ~\{P_{left},\ldots, P_j,P_l\}~. Từ đó, ta có công thức quy hoạch động như sau:

$\displaystyle \begin{cases} dp[0][j][l][k \oplus parity[left][j][l]] = & \displaystyle\sum_{i=left}^{j-1}{(dp[0][i][j][k]} \times 2^{cnt[left][j][l]}) \text{ với } cw(P_{left}, P_i, P_j) \\ dp[1][j][l][k \oplus parity[left][j][l]] = & \displaystyle\sum_{i=left}^{j-1}{(dp[1][i][j][k]} \times 2^{cnt[left][j][l]}) \text{ với } ccw(P_{left}, P_i, P_j) \end{cases}$

Trong đó:

parity[a][b][c] = 0 nếu hai lần diện tích tam giác $\{P_a, P_b, P_c\}$ ~\{P_a, P_b, P_c\}~ là số chẵn, ngược lại parity[a][b][c] = 1.
cnt[a][b][c] là số lượng điểm $P_i (1 \le i \le n)$ ~P_i (1 \le i \le n)~ nằm bên trong tam giác $\{P_a, P_b, P_c\}$ ~\{P_a, P_b, P_c\}~.
$cw(P_a, P_b, P_c)$ ~cw(P_a, P_b, P_c)~ nếu $3$ ~3~ điểm $P_a, P_b, P_c$ ~P_a, P_b, P_c~ theo thứ tự chiều kim đồng hồ và $ccw(P_a, P_b, P_c)$ ~ccw(P_a, P_b, P_c)~ nếu $3$ ~3~ điểm $P_a, P_b, P_c$ ~P_a, P_b, P_c~ 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 $\mathcal{O}(n^4)$ ~\mathcal{O}(n^4)~.

Một số lưu ý trong công thức QHĐ trên:

Việc ta phải nhân với $2^{cnt[left][j][l]}$ ~2^{cnt[left][j][l]}~ đã được đề cập trong nhận xét 2.

Giới hạn của $i$ ~i~ là $left \le i < j$ ~left \le i < j~ chứ không phải $left < i < j$ ~left < i < j~. Việc $i = left$ ~i = left~ do Upper hoặc Lower có thể là một đoạn thẳng (đa giác chỉ có $2$ ~2~ đỉnh). Minh họa ở $2$ ~2~ 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:

$\displaystyle \displaystyle\sum_{left=1}^{n}\Biggl( \sum_{j=left+1}^{n} \biggl( \sum_{k=0}^{1} \Bigl( \sum_{i=left}^{j-1}(dp[0][i][j][k]) \times \sum_{i=left}^{j-1}(dp[1][i][j][k])\Bigl) \biggl) \Biggl) -\displaystyle{n \choose 2}$

Lưu ý rằng ở đáp án, ta phải trừ đi số lượng tập $S$ ~S~ với $|S|=2$ ~|S|=2~ 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

Review in round 7 Câu D

Comments