Link blog gốc

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.