Phân tích: How Big Are the Pockets?

(i). Tính diện tích đa giác

Khi Polygonovich đi bộ, phần bên trong của đa giác luôn nằm ở bên phải ông, hoặc luôn ở bên trái ông. Đây không phải là một sự thật hiển nhiên. Đa giác có thể phức tạp đến mức nếu chỉ nhìn vào một phần của đường đi ở giữa, người ta không có cách nào để quyết định xem bên trái là bên trong hay bên phải là bên trong. Hãy chấp nhận sự thật này và giả định trường hợp đầu tiên -- tay phải của ông luôn chạm vào phần bên trong của đa giác.

Cố định một thanh dọc có độ rộng đơn vị, quan sát sự tương tác giữa \(P\) (đường đi của Polygonovich) và \(B\) (thanh dọc).

• \(P\) cắt \(B\) một số chẵn lần. Bởi vì đường đi là khép kín, và bất cứ khi nào Polygonovich cắt từ trái sang phải, lần tiếp theo ông phải cắt theo hướng ngược lại. Từ trên xuống dưới, chúng ta dán nhãn chúng là lần cắt thứ 1, lần cắt thứ 2, và cứ tiếp tục như vậy.
• Hơn nữa, nhìn xuống \(B\) từ trên cao. Lúc đầu, nó nằm ngoài đa giác. Mỗi khi nó gặp một cạnh của \(P\), nó thay đổi từ trạng thái nằm ngoài đa giác sang nằm trong và ngược lại. Vì vậy, một hình vuông đơn vị trên \(B\) nằm trong đa giác khi và chỉ khi nó nằm giữa một lần cắt thứ \((2k-1)\) và lần cắt thứ \((2k)\).
• Lưu ý rằng nếu đa giác luôn nằm ở phía bên phải, thì chúng ta biết rằng lần cắt thứ \((2k-1)\) luôn là từ trái sang phải, và lần cắt thứ \((2k)\) là từ phải sang trái.

Với bất kỳ hình vuông đơn vị \(U\) nào, chúng ta có thể quyết định xem nó có nằm trong đa giác hay không bằng cách đếm số lần cắt từ trái sang phải theo chiều dọc phía trên \(U\), trừ đi số lần cắt từ phải sang trái phía trên \(U\). Chúng ta có thể có một bộ đếm nhỏ bên trong \(U\), và mỗi khi có một lần cắt từ trái sang phải phía trên \(U\), chúng ta tăng bộ đếm lên 1; và đối với các lần cắt từ phải sang trái, giảm bộ đếm đi 1.

Sau những bài tập tư duy này, chúng ta thực hiện bước nhảy cuối cùng quay lại sự tương tác giữa \(P\) và \(B\). Chúng ta có thể tưởng tượng một hộp bao quanh (bounding box) bên ngoài đa giác để có hữu hạn các bộ đếm, và bây giờ chúng ta xem xét diện tích, nó không gì khác hơn là tổng của tất cả các bộ đếm. Để tính diện tích, chúng ta làm như sau:

Chúng ta luôn giả định phần bên trong luôn nằm ở phía bên phải. Trong trường hợp ngược lại, cạnh cao nhất trên mỗi thanh sẽ là một lần cắt từ phải sang trái, và tất cả các lập luận trên đều tương tự chỉ khác nhau về dấu. Vì vậy, nếu cuối cùng chúng ta thấy \(A\) âm, chúng ta có thể lấy giá trị tuyệt đối của nó để có diện tích đúng.

Chúng ta lưu ý rằng đây chỉ là một trường hợp đặc biệt của thuật toán đơn giản để tính diện tích đa giác nói chung. Tuy nhiên, các hình ảnh chẳng phải rất đẹp trong dạng đặc biệt của lưới nguyên và các cạnh song song với trục tọa độ sao?

(ii). Tính diện tích của đa giác cộng với các túi

Đa giác cộng với các túi tạo thành các hình bậc thang theo bốn hướng (Đông Bắc, Tây Bắc, Đông Nam, Tây Nam). Một chứng minh chính thức sẽ rất dài dòng. Một hình ảnh với một ví dụ tốt là đủ.

Như trong hình, gọi \(A\) là một trong những cạnh cao nhất, \(C\) là cạnh thấp nhất, \(B\) là cạnh xa nhất về bên phải và \(D\) là cạnh xa nhất về bên trái. Chúng ta có 4 hình bậc thang: một từ \(A\) đến \(B\), một từ \(B\) đến \(C\), một từ \(C\) đến \(D\), và một từ \(D\) đến \(A\). Về mặt lý thuyết, chúng được hình thành bởi các điểm cực đại đối với bốn hướng, và mỗi hình bậc thang này có thể được tính toán trong thời gian \(O(m \log m)\), trong đó \(m\) là số điểm trên đa giác. Trong bài toán này, chúng ta sử dụng đảm bảo rằng có tối đa 6000 dải dọc. Đối với mỗi dải dọc \(x\), định nghĩa:

Đối với \(x\) nằm giữa \(A\) và \(B\), \(H(x)\) là giá trị lớn nhất của \(t(x')\) cho tất cả \(x'\) nằm giữa \(x\) và \(B\). Chúng ta có thể tính \(H(x)\) như sau:

H(x) = t(x) for the last strip
for x = (the second last strip) down to A
  H(x) = max(H(x+1), t(x))

Các giá trị trên các hình bậc thang khác có thể được tính toán theo cách tương tự.

Trên dải \(x\), đa giác cộng với các túi là các hình vuông đơn vị nằm giữa \(L(x)\) và \(H(x)\). Vì vậy, chúng ta có thể tính tổng \(H(x) - L(x)\) trên tất cả 6000 dải có thể có và nhận được diện tích của đa giác cùng với các túi.

(iii). Giải quyết bài toán

Kết quả là (ii) trừ đi (i).

Dựa trên phân tích chính thức của Google Code Jam.