Phân tích: Rural Planning

Giới thiệu

Trong bài toán này, chúng ta được cho một tập hợp các điểm trên mặt phẳng 2D. Mục tiêu là xây dựng một đa giác đơn duy nhất sử dụng tất cả các điểm. Để làm cho bài toán thú vị hơn, diện tích của đa giác kết quả có thêm một ràng buộc: nó phải lớn hơn nghiêm ngặt một nửa diện tích của đa giác lớn nhất có thể được xây dựng từ bất kỳ tập con nào của các điểm. Một đa giác chiếm diện tích tối đa nhưng có thể sử dụng một tập con của các điểm luôn là bao lồi (convex hull) của các điểm đó.

Small dataset

Đối với trường hợp dữ liệu nhỏ, chúng ta chọn cách tiếp cận vét cạn để tìm đa giác có diện tích lớn nhất. Giả sử rằng có thể xây dựng một đa giác với diện tích đủ lớn (xem giải thích của trường hợp lớn để biết lý do), đa giác có diện tích cực đại sẽ là một lời giải. Câu hỏi bây giờ trở thành làm thế nào để xây dựng đa giác có diện tích lớn nhất. Chúng ta hoán vị thứ tự của các cọc rào. Đối với mỗi thứ tự, chúng ta kiểm tra xem đa giác có các cạnh cắt nhau hay không (cẩn thận với các cạnh đi qua các cọc rào). Chúng ta giữ lại đa giác có diện tích lớn nhất. Với \(N=10\) cọc rào, việc này tốn không quá \(O(N! \cdot T)\), trong đó \(T\) là thời gian để kiểm tra tính hợp lệ của đa giác và tính diện tích của nó. Việc kiểm tra có thể được thực hiện dễ dàng trong thời gian \(O(N^2)\). Diện tích đa giác có thể được tính trong thời gian \(O(N)\). Vì vậy, thời gian chạy kết quả là \(O(N! \cdot N^2)\). Với \(N=10\), con số này vào khoảng 500 triệu phép tính cơ bản, tương đối nhanh.

Large dataset

Đối với trường hợp lớn, \(N = 1000\), việc vét cạn ngay cả một tập con các hoán vị cọc rào cũng quá tốn kém. Một thuật toán trên \(O(N^3)\) có thể mất quá nhiều thời gian để tính toán. Chúng ta khám phá một phương pháp trực tiếp hơn.

Như đã đề cập trước đó, đa giác có diện tích lớn nhất có thể sử dụng một tập con của các cọc rào là bao lồi. Giả sử chúng ta chia bao lồi thành hai đa giác, một trong hai đa giác này phải chứa ít nhất một nửa diện tích của bao lồi. Lưu ý rằng bất kể bao lồi được chia như thế nào, một trong các đa giác kết quả luôn có diện tích ít nhất bằng một nửa.

Giả sử chúng ta có cách để chia bao lồi bằng cách sử dụng các cọc rào bên trong. Điều này tạo ra một đa giác có diện tích ít nhất bằng một nửa diện tích của bao lồi, và có ít nhất một đỉnh bị cô lập ở bên ngoài đa giác. Chúng ta chỉ cần nối các đỉnh cô lập vào đa giác mà không làm xuất hiện các cạnh cắt nhau. Quá trình này chỉ có thể làm tăng thêm diện tích cho đa giác, do đó đa giác cuối cùng sẽ lớn hơn nghiêm ngặt một nửa diện tích của bao lồi.

Lấy quan sát trên làm cơ sở cho giải pháp, chúng ta có thể chia bao lồi thành nửa trên và nửa dưới một cách tùy ý.

Lưu ý rằng hợp của đa giác trên và dưới chứa toàn bộ diện tích của bao lồi. Hơn nữa, đường đi bên trong không thể gây ra các cạnh cắt nhau vì chúng ta đã chọn sắp xếp các điểm từ trái sang phải (lưu ý, cần xử lý đặc biệt khi có các điểm cùng hoành độ). Một trong hai đa giác này có diện tích ít nhất bằng một nửa bao lồi, như đã giải thích ở trên.

Như đã đề cập, đa giác lớn hơn trong hai đa giác sẽ không chứa tất cả các điểm. Tuy nhiên, chúng ta có thể mở rộng đa giác để sử dụng tất cả các điểm. Điều này được thực hiện bằng cách thêm dần từng điểm vào đa giác. Vì tất cả các điểm bên ngoài đều nằm trên bao lồi, đa giác phải tăng diện tích khi chúng ta làm điều này. Các điểm được thêm vào đa giác bằng cách lấy một điểm bên ngoài và "nối" nó với điểm bên trái và bên phải của nó trên đường gấp khúc chia bao lồi. Để tối ưu hóa, các điểm bên ngoài có thể được thêm vào cùng lúc với việc tạo đường gấp khúc nếu bạn biết các điểm bên ngoài khi xây dựng đường gấp khúc.

Các trường hợp đặc biệt

Ở ví dụ bên trái, điểm cực tả và cực hữu được nối với nhau. Trong trường hợp này, bao lồi được chia thành toàn bộ đa giác và một đoạn thẳng. Toàn bộ đa giác, hay chính là bao lồi, có thể được sử dụng làm câu trả lời cuối cùng.

Trường hợp đặc biệt thứ hai, ở bên phải phía trên, có thể xảy ra khi các điểm có cùng tọa độ \(x\) và khái niệm "từ trái sang phải" không được xác định rõ ràng. Một cách thanh lịch để xử lý trường hợp này là chiếu tất cả các điểm lên một đường thẳng "gần như nằm ngang" và giữ các giá trị hình chiếu vô hướng. Nếu chúng ta chọn một đường thẳng không song song hoặc vuông góc với đường thẳng tạo bởi bất kỳ hai điểm nào trong đầu vào, thì mỗi điểm được chiếu sẽ có một vị trí duy nhất trên đường "nằm ngang". Một đường thẳng đi qua các điểm \((0,0)\) và \((200000,1)\) sẽ hoạt động tốt.

Khi tất cả các điểm đã được chiếu lên đường thẳng, thứ tự sắp xếp của các điểm được xác định bởi giá trị hình chiếu. Nếu chúng ta lấy một tập hợp các điểm và đi qua chúng theo thứ tự này, chúng ta sẽ tạo thành một đường gấp khúc.

Chúng ta có thể chỉ ra rằng việc chạy thuật toán này bao gồm hai điểm đầu mút của một trong các nửa bao lồi và tất cả các điểm ở giữa sẽ tạo ra một đa giác kín. Lưu ý rằng khi bạn cũng mở rộng tập hợp ở giữa để chứa tất cả các điểm nằm trong các nửa bao lồi, đa giác sẽ tăng kích thước. Điều này là do các điểm được thêm vào nằm bên ngoài đa giác hiện tại của chúng ta theo tính chất của nửa bao lồi. Một đường thẳng đi từ các điểm ở giữa sẽ di chuyển ra xa đa giác đầu tiên về phía bao lồi và quay trở lại các điểm ở giữa khi đi theo thứ tự của chúng ta. Kỹ thuật này đảm bảo rằng diện tích đa giác của chúng ta lớn hơn đa giác chỉ có các điểm ở giữa.

Tổng kết

Để tóm tắt giải pháp, chúng ta sẽ nhắc lại các bước chính của thuật toán:

• Lấy đầu vào và chia nó thành ba tập hợp điểm bằng đường thẳng nối \((0,0)\) đến \((200000,1)\):
  • Bao lồi trên (upper hull)
  • Bao lồi dưới (lower hull)
  • Các điểm ở giữa (middle points)
• Chạy thuật toán đóng kín sử dụng bao lồi trên và kết hợp bao lồi dưới cùng các điểm ở giữa.
• Chạy thuật toán đóng kín sử dụng bao lồi dưới và kết hợp bao lồi trên cùng các điểm ở giữa.
• In ra giải pháp có đa giác lớn hơn.

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