Vào lúc 8h tối thứ tư tuần này (08/06/2022), mình sẽ tổ chức buổi trình bày thứ hai trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Chủ đề của buổi thứ hai là "Đánh giá hiệu quả thuật toán." Để có thể theo dõi bài trình bày này, bạn cần nắm được cách chứng minh mệnh đề chứa dấu ~\forall, \exists~ và mệnh đề "nếu ... thì ..." (đã được trình bày ở bài đầu tiên), nắm được khái niệm thuật toán, và biết một số bất đẳng thức đơn giản như ~\forall x \in \mathbb{R}: x^2 \geq 0~ và bất đẳng thức trung bình cộng - trung bình nhân.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

• Cách phân tích độ phức tạp của một thuật toán.
• Biểu diễn độ phức tạp bằng kí pháp chữ ~O~ lớn. Sử dụng kí pháp chữ ~O~ lớn để đánh giá xem thuật toán có chạy đủ nhanh trong thời gian quy định hay không.
• Một số kĩ thuật tăng tốc độ chạy của thuật toán như lợi dụng hằng số nhỏ của ~\sum i^k~, sử dụng bitset, hai con trỏ, và chia căn đơn giản.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.

Bài 1:

Phần a:

~P = \sqrt[3]{7 + 5\sqrt{2}} + \sqrt[3]{7 - 5\sqrt{2}}~

Sử dụng hằng đẳng thức ~(a+b)^3 = a^3 + b^3 +3ab(a+b)~ với ~a = \sqrt[3]{7 + 5\sqrt{2}}~ và ~b = \sqrt[3]{7 - 5\sqrt{2}}~, ta có

~P^3 = (7 + 5\sqrt{2}) + (7 - 5\sqrt{2}) + 3\sqrt[3]{7 + 5\sqrt{2}}\sqrt[3]{7 - 5\sqrt{2}}(\sqrt[3]{7 + 5\sqrt{2}} + \sqrt[3]{7 - 5\sqrt{2}})~

~\Rightarrow P^3 = 14 +3\sqrt[3]{49-25 \times 2}P~

~\Rightarrow P^3 = 14 - 3P~

~\Rightarrow P^3 - 3P - 14 = 0~

Ta thấy ~2~ là một nghiệm của phương trình ẩn ~P~ này nên

~P^3 - 2P^2 + 2P^2 - 4P + 7P - 14 = 0~

~\Rightarrow (P-2)(P^2 + 2P + 7) = 0~

~\Rightarrow (P-2)((P+1)^2 + 6) = 0~

Do ~(P+1)^2 + 6 \geq 6 > 0~ nên ~P - 2 = 0 \Rightarrow \boxed{P = 2}~

Phần b:

Giả sử ~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

Do ~0 \in \mathbb{Z}, P(0) \in \mathbb{Z}~ nên ~c \in \mathbb{Z}~

Do ~1 \in \mathbb{Z}, P(1) \in \mathbb{Z}~ nên ~a + b + c \in \mathbb{Z}~. Do ~\begin{cases} c \in \mathbb{Z} \\ a + b + c \in \mathbb{Z} \end{cases} \Rightarrow (a+b+c) - c \in \mathbb{Z} \Rightarrow a + b \in \mathbb{Z}~

Do ~-1 \in \mathbb{Z}, P(-1) \in \mathbb{Z}~ nên ~a - b + c \in \mathbb{Z}~.

Do ~\begin{cases} a+b+c \in \mathbb{Z} \\ a - b + c \in \mathbb{Z} \end{cases}~ nên ~2a + 2c \in \mathbb{Z}~.

Do ~c \in \mathbb{Z}~ nên ~-2c \in \mathbb{Z}~

Do ~\begin{cases} 2a + 2c \in \mathbb{Z} \\ -2c \in \mathbb{Z} \end{cases}~ nên ~2a \in \mathbb{Z}~

Ta có thể kết luận:

~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z} \Rightarrow \begin{cases} 2a \in \mathbb{Z} \\ a + b \in \mathbb{Z} \\ c \in \mathbb{Z} \end{cases}~

Giả sử ~2a, a+b, c \in \mathbb{Z}~, ta cần chứng minh ~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

Chọn số ~x \in \mathbb{Z}~ bất kì.

Do ~2a \in \mathbb{Z}~, hoặc ~a \in \mathbb{Z}~ hoặc ~a = \frac{m}{2}~ với ~m \in \mathbb{Z}~

Trường hợp 1: Giả sử ~a \in \mathbb{Z}~.

Do ~\begin{cases} a + b \in \mathbb{Z} \\ a \in \mathbb{Z} \end{cases}~ nên ~b \in \mathbb{Z}~

Do ~a,b,c,x \in \mathbb{Z}~ nên ~P(x) \in \mathbb{Z}~

Trường hợp 2: Giả sử ~a = \frac{m}{2}~ với ~m \in \mathbb{Z}~

Do ~a+b \in \mathbb{Z}~, điều này nghĩa là ~b = \frac{n}{2}~ với ~n \in \mathbb{Z}~

Khi đó ~P(x) = \frac{m}{2}x^2 + \frac{n}{2}x + c~

Do ~x \in \mathbb{Z}~ nên ~x = 2k~ hoặc ~x = 2k+1~ với ~k \in \mathbb{Z}~

Trường hợp 2.1: Nếu ~x = 2k~ thì ~P(x) = \frac{m}{2}4k^2 + \frac{n}{2}2k + c = m(2k^2) + nk + c \in \mathbb{Z}~

Trường hợp 2.2: Nếu ~x = 2k+1~ thì ~P(x) = \frac{m}{2}(4k^2 + 2k + 1) + \frac{n}{2}(2k+1) + c = m(2k^2 + k) + \frac{m}{2} + nk + \frac{n}{2} + c = m(2k^2 + k) + a + nk + b + c \in \mathbb{Z}~

Tổng hợp hai trường hợp 2.1 và 2.2, ta được ~P(x) \in \mathbb{Z}~

Do ở cả hai trường hợp, ta được ~P(x) \in \mathbb{Z}~ và ta chọn số ~x \in \mathbb{Z}~ bất kì, ta có thể kết luận

~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

và đây là điều phải chứng minh.

Bài 4:

Giả sử có cách viết 10 số thỏa mãn yêu cầu bài toán.

Đánh số các điểm như hình dưới đây

Ta có:

~a_1 + a_5 + a_2 = a_1 + a_8 + a_4 = ... = k~

~\Rightarrow 3(a_1 + a_2 + a_3 + a_4) + a_5 + a_6 + a_7 + a_8 + a_9 + a_{10} = 6k~

~\Rightarrow 2(a_1 + a_2 + a_3 + a_4) + \sum_{i=1}^{10} a_i = 6k~

~\Rightarrow 2(a_1+a_2+a_3+a_4) + 45 = 6k~

~\Rightarrow 45 = 2(3k + a_1 + a_2 + a_3 + a_4) \Rightarrow 2 \mid 45~ (vô lí)

Do đó, giả sử ban đầu sai. Nói cách khác, không có cách viết 10 số thỏa mãn yêu cầu bài toán.

Bài 5:

Phần a:

Gọi 5 điểm được cho là ~A_1, A_2, A_3, A_4, A_5~

Gọi ~H~ là tập các đỉnh của bao lồi của ~5~ điểm được cho. Do không có 3 điểm nào thẳng hàng, ~3 \leq |H| \leq 5~

Trường hợp 1: ~|H| = 3~

Không làm mất tính tổng quát, giả sử ~H = \{A_1, A_2, A_3\}~. Khi đó, ~A_4~ nằm trong tam giác ~A_1A_2A_3~

~\Rightarrow \angle A_1A_4A_2 + \angle A_2A_4A_3 + \angle A_3A_4A_1 = 360^o~

Khi đó, một trong ba góc này sẽ phải lớn hơn hoặc bằng ~120^o~, tức lớn hơn ~90^o~. Không làm mất tính tổng quát, giả sử góc đó là ~\angle A_1A_4A_2~. Khi đó tam giác ~A_1A_4A_2~ là tam giác tù, tức ta tìm được một tam giác tù.

Trường hợp 2: ~|H| = 4~

Không làm mất tính tổng quát, giả sử bao lồi là tứ giác ~A_1A_2A_3A_4~. Khi đó, ~A_5~ nằm trong tứ giác ~A_1A_2A_3A_4~

~\Rightarrow \angle A_1A_5A_2 + \angle A_2A_5A_3 + \angle A_3A_5A_4 + \angle A_4A_5A_1 = 360^o~

Giả dụ cả bốn góc này không có góc tù nào. Khi đó, cả bốn góc đều có số đo ~90^o~. Ta sẽ có ~\angle A_1A_5A_2 + \angle A_2A_5A_3 = 180^o \Rightarrow \angle A_1A_5A_3 = 180^o \Rightarrow A_1, A_5, A_3~ thẳng hàng, trái với giả thiết ban đầu rằng không có ba điểm nào thẳng hàng. Vì thế giả dụ ban đầu sai, tức ít nhất một trong bốn góc phải là góc tù, và vì thế ta tìm được một tam giác tù.

Trường hợp 3: ~|H| = 5~

Không làm mất tính tổng quát, giả sử bao lồi là đa giác ~A_1A_2A_3A_4A_5~. Do đây là đa giác lồi, ta có

~\sum_{i=1}^5 \angle A_i = 180 \times 3 = 540^o~

Do ~\frac{540^o}{5} = 108^o~, sẽ có ít nhất một góc lớn hơn hoặc bằng ~108^o~, tức một góc lớn hơn ~90^o~. Không làm mất tính tổng quát, giả sử góc đó là góc ~A_1A_2A_3~, khi đó tam giác ~A_1A_2A_3~ tù.

Từ ba trường hợp trên, ta có thể kết luận rằng cho 5 điểm bất kì trên mặt phẳng sao cho không có ba điểm nào thẳng hàng, ta có thể tìm được một tam giác có đỉnh là 3 trong 5 điểm được cho.

Phần b:

Gọi 2022 điểm được cho là ~A_1, A_2, A_3, A_4, ..., A_{2022}~

Gọi ~H~ là tập đỉnh của bao lồi của 2022 điểm được cho. Do không có 3 điểm nào thẳng hàng, ~3 \leq |H| \leq 2022~.

Gọi ~k~ là số điểm nằm trong bao lồi. Ta có ~k = 2022 - |H|~

Nếu ~|H| \leq 4~ thì ~k \geq 2018~. Với mỗi điểm trong bao lồi, ta có thể tìm được một tam giác tù có điểm đó là đỉnh và hai đỉnh còn lại là hai đỉnh của đa giác bao lồi, và vì thế ta tìm được ít nhất ~k~ tam giác tù. Do ~k \geq 2018~, ta có điều phải chứng minh.

Xét trường hợp ~|H| \leq 5~.

Không làm mất tính tổng quát, giả sử bao lồi là đa giác ~A_1A_2A_3...A_n~ (~n = |H| = 2022 - k~)

Chia đa giác thành các tam giác ~A_1A_2A_3~, ~A_1A_3A_4~, ..., ~A_1A_{n-1}A_n~. Do không có ba điểm nào thẳng hàng, mỗi điểm trong bao lồi sẽ nằm trọn trong một trong các đa giác này, và từ đó với mỗi điểm trong bao lồi, ta tìm được một tam giác tù có điểm đó là một đỉnh và hai đỉnh còn lại là hai đỉnh của tam giác chứa nó (và đồng thời là hai đỉnh của đa giác bao lồi). Nói cách khác, ta tìm được ~k~ tam giác tù.

Ta có:

~\sum_{i=1}^n \angle A_i = 180(n-2)~

Giả dụ có nhiều hơn 4 góc không tù. Không làm mất tính tổng quát, giả sử các góc ~A_1, A_2, A_3, A_4, A_5~ là các góc không tù, khi đó ~\sum_{i=6}^n \angle A_i > 180(n-2) - 450 = 180(n - \frac{9}{2})~

Nếu ~n = 5~ thì điều này nghĩa là ~0 > 90~, vô lí.

Nếu ~n > 5~ thì điều này nghĩa là có một góc ~\angle A_i \geq \frac{180(n-\frac{9}{2})}{n-5}~. Mà khi ~n > 5~, ~\frac{180(n-\frac{9}{2})}{n-5} > 180~ nên ~\angle A_i > 180^o~. Điều này vô lí do một góc của một đa giác lồi không thể có số đo vượt quá ~180^o~

Do cả hai trường hợp đều dẫn đến điều vô lí, điều này nghĩa là có nhiều nhất 4 góc không tù, tức đa giác bao lồi có ít nhất ~n - 4~ góc tù. Mỗi một góc tù sẽ tạo ra một tam giác tù nên ta có ít nhất ~n - 4~ tam giác tù.

Tổng số tam giác tù ít nhất là ~k + (n-4) = n+k - 4 = 2022 - 4 = 2018~, tức là ta sẽ tìm được ít nhất 2018 tam giác tù.

Kết hợp hai trường hợp, ta có được điều phải chứng minh.

Vào lúc 8h tối thứ Ba ngày 31 tháng 5 năm 2022, mình sẽ tổ chức buổi trình bày đầu tiên trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Chủ đề của buổi đầu tiên là "Phương pháp chứng minh." Để có thể nắm được nội dung bài trình bày, bạn chỉ cần biết trước về tập hợp số tự nhiên và tính chia hết, không nhất thiết phải biết lập trình.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

• Các khái niệm logic đơn giản như "không" (not), "hoặc" (or), "và" (and), mệnh đề kéo theo, mệnh đề tương đương, với mọi, tồn tại
• Tập hợp và hàm số
• Ba phương pháp chứng minh phổ biến là phương pháp chia trường hợp, phương pháp phản chứng, và phương pháp quy nạp.

Mục tiêu của bài trình bày là giúp bạn:

• Đọc hiểu được định nghĩa Toán học (ví dụ định nghĩa chữ O lớn, định nghĩa đồ thị, định nghĩa cây), làm nền tảng cho các buổi trình bày tiếp theo.
• Giải thích tại sao một tập số nguyên dương khác rỗng luôn có số nhỏ nhất?
• Nắm được cách chứng minh "tương đương" hoặc chứng minh "bằng nhau"
• Nắm được cách dùng quy nạp để chứng minh các tính chất mà bạn mò ra được bằng tay khi xem xét các trường hợp nhỏ.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Xem tư liệu bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.

Cho một cây vô hướng ~T = (V, E, w)~ với ~w > 0~

Gọi ~s, t \in V~ là hai đầu mút của đường kính của ~T~

Chứng minh rằng: Đường đi đơn dài nhất trên ~T~ xuất phát từ một nút ~u \in V~ là đường đi từ ~u~ đến ~s~ hoặc đường đi từ ~u~ đến ~t~

Chứng minh

Chọn ~u \in V~ bất kì.

Đặt ~u~ làm gốc cây ~T~

Giả dụ đường đi đơn dài nhất trên ~T~ xuất phát từ ~u~ không là đường đi từ ~u~ đến ~s~ và cũng không là đường đi từ ~u~ đến ~t~ mà là đường đi từ ~u~ đến ~v~ với ~v \in V, v \ne s, v \ne t~.

Đặt ~a = \text{lca}(v,s), b = \text{lca}(s,t)~

Do ~a \rightarrow s~ và ~b \rightarrow s~, một trong hai trường hợp sau sẽ xảy ra:

Trường hợp 1: ~a \rightarrow b~

Khi đó, ~\begin{cases} a \rightarrow b \\ b \rightarrow t \end{cases} \Rightarrow a \rightarrow t~

Ta có: ~f(u,v) > f(u,t) \Rightarrow f(u,a) + f(a,v) > f(u,a) + f(a,t)~ (do ~a \rightarrow v~ và ~a \rightarrow t~) ~\Rightarrow f(a,v) > f(a,t)~

Do ~a \rightarrow b \rightarrow t~, ~f(a,t) \geq f(b,t)~

Ta có: ~f(s,t) = f(s,b) + f(b,t) \leq f(s,a) + f(a,t) < f(s,a) + f(a,v) = f(s,v)~

Điều này nghĩa là đường đi từ ~s~ tới ~t~ không là đường kính của ~T~ (do có đường đi từ ~s~ tới ~v~ dài hơn), trái với giả thiết ban đầu

Trường hợp 2: ~b \rightarrow a~

Đầu tiên, ta cần chứng minh ~lca(v,t) = b~.

~\begin{cases} b \rightarrow a \\ a \rightarrow v \end{cases} \Rightarrow b \rightarrow v~

~b = \text{lca}(s,t) \Rightarrow b \rightarrow t~

Giả dụ tồn tại ~c \in V~ sao cho ~c \rightarrow v~ và ~c \rightarrow t~ và ~b \rightarrow c~. Do ~a,b,c \rightarrow v~ và ~b \rightarrow c~, hoặc ~c \rightarrow a~ hoặc ~a \rightarrow c~.

Nếu ~c \rightarrow a~ thì với việc ~a \rightarrow s~, ~c \rightarrow s~. Do ~c \rightarrow s~ và ~c \rightarrow t~ và ~b \rightarrow c~, ~b \ne \text{lca}(s,t)~ nên trường hợp này không thể xảy ra.

Nếu ~a \rightarrow c~ thì do ~c \rightarrow t~, ~a \rightarrow t~. Điều này cộng với việc ~a \rightarrow s~ nghĩa là ~a~ là một cha chung của ~t~ và ~s~. Do ~b = \text{lca}(s,t)~, ~a \rightarrow b~, trái với điều kiện của trường hợp 2.

Do hai trường hợp đều không thể xảy ra, giả dụ tồn tại ~c \in V~ sai. Điều này đồng nghĩa với việc ~lca(v,t) = b~

Ta có:

• ~f(u,v) > f(u,s) \Rightarrow f(u,a) + f(a,v) > f(u,a) + f(a,s) \Rightarrow f(a,v) > f(a,s)~
• ~f(v,t) = f(v,a) + f(a,b) + f(b,t) > f(s,a) + f(a,b) + f(b,t) = f(s,t)~

Do đó, đường đi từ ~s~ đến ~t~ không thể là đường kính của ~T~, trái với giả thiết ban đầu.

Do cả trường hợp 1 và trường hợp 2 đều không thể xảy ra, giả dụ ban đầu sai.

Ta giờ có thể kết luận

~\forall u \in V:~ Một đường đi đơn dài nhất xuất phát từ đỉnh ~u~ là đường đi từ ~u~ đến ~s~, hoặc là đường đi từ ~u~ đến ~t~

Hệ quả của định lí:

• Định lí này chứng minh tính đúng đắn của thuật toán tìm đường kính của cây
• Để tìm một đường đi dài nhất xuất phát từ ~u~, ta có thể tìm đường kính từ ~s~ đến ~t~ rồi xét hai đường đi từ ~s~ đến ~u~ và từ ~t~ đến ~u~

Cho một cây vô hướng ~T = (V, E, w)~ thỏa mãn ~w > 0~

Gọi ~L \subset V, L \ne \emptyset~ là một tập nút đặc biệt của cây

Gọi ~d_i~ là độ dài đường đi đơn dài nhất từ nút ~i~ đến một nút trong tập ~L~. Nói cách khác, ~d_i = \max_{x \in L} f(x,i)~ với ~f: V \times V \rightarrow \mathbb{R}, (x,y) \mapsto \text{độ dài đường đi đơn từ } x \text{ đến } y~

Lưu ý nếu ~i \in L~ thì ~d_i \ne 0~ hoàn toàn có thể xảy ra do có thể tồn tại đường đi đơn giữa hai nút trong tập ~L~.

Chọn một nút ~r~ thỏa mãn ~\forall u \in V: d_r \leq d_u~ là nút gốc của cây.

Nếu nút ~x~ là tổ tiên của nút ~y~, ta kí hiệu ~x \rightarrow y~

Chứng minh rằng ~\forall x,y \in V, x \rightarrow y: d_x \leq d_y~

Bổ đề

~\forall x \in V, x \ne r: \forall y \in L, x \rightarrow y: d_x \ne f(x,y)~

Chứng minh bổ đề

Chọn nút ~x, y~ bất kì sao cho ~x \in V, x \ne r, y \in L, x \rightarrow y~

Do ~\forall u \in V: d_r \leq d_u~ và ~x \in V~, ~d_r \leq d_x~

Giả dụ ~d_x = f(x,y)~.

Do ~r~ là gốc, ~r \rightarrow x~. Do ~\begin{cases} r \rightarrow x \\ x \rightarrow y \end{cases}~ nên ~f(r,y) = f(r,x) + f(x,y)~.

Do ~y \in L~ và ~d_r = \max_{i \in L} f(r,i)~, ~d_r \geq f(r,y)~

Do ~w > 0~, ~f(r,x) > 0~ nên ~f(r,x) + f(x,y) > f(x,y)~

Do ~\begin{cases} d_r \geq f(r,y) \\ f(r,y) = f(r,x) + f(x,y) \\ f(r,x) + f(x,y) > f(x,y) \\ d_x = f(x,y) \end{cases}~ nên ~d_r > d_x~

Tuy nhiên, điều này trái với ~d_r \leq d_x~. Do đó, giả dụ ban đầu sai, tức ~d_x \ne f(x,y)~

Do cách chọn ~x, y~, ta kết luận được

~\forall x \in V, x \ne r: \forall y \in L, x \rightarrow y: d_x \ne f(x,y)~

và đây là điều phải chứng minh

Quay lại bài toán

Chọn ~x,y \in V~ bất kì sao cho ~x \rightarrow y~.

Nếu ~x = r~, ta có điều phải chứng minh

Nếu ~x \ne r~, theo bổ đề đã chứng minh ở trên, ~d_x = f(x,t)~ với ~t \in L, x \nrightarrow t~.

Ta có thể chọn nút ~a = \text{lca}(x,t)~ thỏa mãn ~a \rightarrow x~, ~a \rightarrow t~ và ~f(x,t) = f(x,a) + f(a,t)~

Do ~\begin{cases} a = \text{lca}(x,t) \\ x \nrightarrow t \\ x \rightarrow y \end{cases}~ nên ~a = \text{lca}(y,t)~

Do đó ~f(y,t) = f(y,a) + f(a,t)~

Do ~\begin{cases} a \rightarrow x \\ x \rightarrow y \end{cases}~ nên ~f(y,a) = f(y,x) + f(x,a)~

Vì thế nên ~f(y,t) = f(y,x) + \Big(f(x,a) + f(a,t)\Big) = f(y,x) + f(x,t) = f(y,x) + d_x~

Do ~w > 0~ nên ~f(y,x) \geq 0 \Rightarrow f(y,x) + d_x \geq d_x~ và vì thế ~f(y,t) \geq d_x~

Do ~t \in L~ và ~d_y = \max_{i \in L} f(y,i)~, ~d_y \geq f(y,t)~

~\begin{cases} f(y,t) \geq d_x \\ d_y \geq f(y,t) \end{cases} \Rightarrow d_y \geq d_x~

Do cách chọn ~x, y~, ta có thể kết luận

~\forall x,y \in V, x \rightarrow y: d_x \leq d_y~

Đây là điều phải chứng minh.

Link bài tập

Do đa giác không tự cắt, nếu các cạnh không thẳng đứng thì ta có thể coi các cạnh là các hàm số. Ta có định lí sau:

Cho hai hàm ~f, g~ liên tục trên ~(l,r)~ sao cho ~f(x) - g(x) = 0~ vô nghiệm trên ~(l,r)~. Lấy điểm ~x_0 \in (l,r)~. Nếu ~f(x_0) < g(x_0)~ thì ~f < g~ trên ~(l,r)~

Do đó, nếu không có các cạnh thẳng đứng thì khi dùng một đường quét từ trái sang phải, ta có thể đưa các cạnh cắt đường quét vào một pbds tree và so sánh các cạnh bằng tung độ giao điểm của các cạnh và đường quét. Khi di chuyển đường quét, ta chỉ cần loại bỏ các cạnh không còn cắt với đường quét ra khỏi pbds tree (so sánh bằng cách tính tung độ giao điểm ở đường quét cũ), thêm các cạnh mới vào pbds tree (so sánh bằng cách tính tung độ giao điểm tại đường quét mới) mà không cần phải sắp xếp lại thứ tự các đoạn vì thứ tự các đoạn sẽ không thay đổi. Với mỗi điểm truy vấn, ta đếm số cạnh nằm dưới điểm đó trong pbds tree bằng cách dùng hàm order_of_key (nói cách khác, đếm số đoạn mà tia thẳng đứng xuống dưới có gốc là điểm truy vấn cắt đa giác). Từ số điểm này, ta sẽ biết được điểm nằm trong đa giác hay không nếu tia này không đi qua đỉnh nào của đa giác.

Vậy làm thế nào để không có các cạnh thẳng đứng hay các tia đi qua đỉnh của đa giác. Ta xoay đa giác và các điểm một góc ~\alpha~ quanh gốc tọa độ sao cho ~\sin\alpha~ và ~\cos\alpha~ sao cho ~x\sin\alpha + y\cos\alpha = 0~ không có nghiệm nguyên ~(x,y)~ thỏa mãn ~|x| \leq 2 \times 10^9~ và ~|y| \leq 2 \times 10^9~. Dễ dàng kiểm tra được ~\alpha = 1~ là một góc thỏa mãn điều kiện này. Sau khi xoay, các điểm khác nhau trong input sẽ có hoành độ khác nhau. Điều này nghĩa là khi ta vẽ một đường thẳng đứng đi qua điểm được truy vấn, đường thẳng đó sẽ không đi qua đỉnh đa giác nào trừ phi điểm truy vấn là đỉnh của đa giác (nhưng ta có thể dễ dàng kiểm tra một điểm có phải đỉnh của đa giác hay không)

Như vậy tổng hợp lại ta cần làm như sau:

• Đọc hết input
• Với các điểm truy vấn mà là đỉnh của đa giác, lưu đáp án của điểm đó là "YES". ~O(q\log(n))~
• Với các điểm nằm trên cạnh thẳng đứng, lưu đáp án của điểm đó là "YES". ~O((q+n)\log(n))~
• Sử dụng thuật toán dùng pbds tree trình bày ở trên với các cạnh không thẳng đứng để xác định các điểm nằm trên cạnh vì các điểm này dễ bị sai số khi xoay, gây ra đáp án không chính xác. Lưu ý do các điểm có tọa độ nguyên trong ~[-10^9, 10^9]~, ta nên dùng phân số có tử và mẫu kiểu long long để tính toán và so sánh. ~O((n+q)\log(n))~
• Xoay đa giác và các điểm một góc ~\alpha = 1~ quanh gốc tọa độ. ~O(n+q)~
• Dùng đường quét để thêm, bớt các cạnh đã xoay (đã được đảm bảo không có cạnh thẳng đứng), khi quét đến điểm truy vấn nào, đếm số cạnh nằm dưới điểm truy vấn đó để có đáp án. ~O((n+q)\log(n))~

Vậy tổng độ phức tạp là ~O((q+n)\log(n))~. Tuy nhiên, do có nhiều bước nên hằng số của thuật toán khá lớn, cần lập trình cẩn thận tránh bị quá thời gian.

Code mẫu (369 dòng)

Bài này mình code mất 3 ngày -_-, nhưng mà trong quá trình code mình cũng ngộ ra được nhiều kinh nghiệm cho bản thân.

Một số bài tập tương tự sử dụng định lí trên:

• NAC 2020 - Bomas
  • Đội mình tạch vì lao vào bài này, nên mình nhớ định lí trên khá lâu
• Timus - Light
  • Bài này có điều kiện đa giác đơn giản (tức đa giác không tự cắt). Nói chung khi nào bạn thấy điều kiện đa giác không tự cắt mà phải thực hiện nhiều truy vấn thì rất nên nhớ đến định lí này.