Phân tích: Irregular Cakes

Trước khi bắt đầu giải quyết bài toán, trước tiên chúng ta cần biết cách tính diện tích của chiếc bánh để biết mỗi người dự tiệc sẽ ăn bao nhiêu bánh. Theo các ràng buộc, chúng ta được đảm bảo đây là một đa giác không tự cắt, vì vậy chúng ta có thể sử dụng công thức:

Để công thức này hoạt động, điểm đầu tiên và điểm cuối cùng trong đa giác phải là cùng một điểm. Tức là, \(X_0 = X_N\) và \(Y_0 = Y_N\). Danh sách các điểm cũng phải theo thứ tự ngược chiều kim đồng hồ. Điều này có thể đạt được bằng cách duyệt qua tất cả các điểm trong biên dưới \(L\), sau đó duyệt qua tất cả các điểm trong biên trên \(U\) theo thứ tự ngược lại.

Khi đã biết tổng diện tích của chiếc bánh, chúng ta cần xác định lượng bánh cần chia cho mỗi khách. Vì có \(G\) khách, chúng ta có thể tính toán con số này một cách đồng đều là \(\text{Diện tích mỗi khách} = \text{Tổng diện tích} / G\).

Cuối cùng, chúng ta đã sẵn sàng để xác định vị trí cắt bánh. Bài toán này có thể được giải quyết theo nhiều cách khác nhau, nhưng ở đây chúng ta sẽ thảo luận về việc sử dụng tìm kiếm nhị phân (binary search) vì đây thường là thuật toán đơn giản nhất để lập trình.

Để có được một miếng bánh có diện tích là \(\text{Diện tích mỗi khách}\), chúng ta biết rằng nhát cắt thẳng đứng sẽ có tọa độ \(X\) nằm trong khoảng từ \(0\) đến \(W\), vì vậy chúng ta thực hiện tìm kiếm nhị phân trên phạm vi này.

Đối với mỗi điểm cắt thử nghiệm trong quá trình tìm kiếm, chúng ta tính diện tích của phần bánh nằm bên trái nhát cắt đó.

• Nếu nó tạo ra một miếng bánh có diện tích lớn hơn \(\text{Diện tích mỗi khách}\), chúng ta cập nhật cận trên của phạm vi tìm kiếm.
• Nếu chúng ta chọn một nhát cắt tạo ra một miếng bánh có diện tích nhỏ hơn hoặc bằng \(\text{Diện tích mỗi khách}\), chúng ta cập nhật cận dưới của phạm vi tìm kiếm.

Quá trình tìm kiếm này cuối cùng sẽ hội tụ về điểm cắt chính xác với độ chính xác đủ lớn.

Nếu \(G=2\), chúng ta đã hoàn thành. Nếu \(G > 2\), thì tìm kiếm nhị phân có thể được lặp lại để tìm các nhát cắt khác. Điểm cắt thứ hai nên được đặt sao cho diện tích bánh bên trái nhát cắt đó là \(\text{Diện tích mỗi khách} \times 2\), điểm cắt thứ ba nên được đặt sao cho diện tích bánh bên trái nhát cắt đó là \(\text{Diện tích mỗi khách} \times 3\), và cứ tiếp tục như vậy.

Tại mỗi bước lặp của tìm kiếm nhị phân, chúng ta cần tính diện tích của một đa giác sử dụng một phần của \(L\), \(U\), và một đường thẳng tại một tọa độ \(X\) bất kỳ, việc này đòi hỏi nhiều công sức hơn là tính diện tích của toàn bộ chiếc bánh. Điều đầu tiên cần lưu ý là chúng ta có thể sử dụng tất cả các điểm trong \(L\) và \(U\) có tọa độ \(X\) sao cho \(0 \le X_i \le X_{\text{cut}}\), trong đó \(X_i\) là tọa độ \(X\) của điểm \(i\), và \(X_{\text{cut}}\) là tọa độ \(X\) của nhát cắt. Tiếp theo, chúng ta cần xác định tọa độ \(Y\) của các điểm tại \(X_{\text{cut}}\) trên \(L\) và \(U\). Nếu chúng ta tìm thấy hai điểm liên tiếp \(A\) và \(B\) trong \(L\) sao cho \(A_x \le X_{\text{cut}}\) và \(B_x \ge X_{\text{cut}}\), chúng ta có thể sử dụng nội suy tuyến tính để tìm giao điểm của đoạn thẳng \(AB\) và đường thẳng đứng xác định bởi \(X_{\text{cut}}\). Khi đã biết hai điểm mới này, diện tích của phần bánh bị cắt có thể được tính toán.

Bài toán này cũng có thể được giải quyết bằng giải pháp thời gian tuyến tính \(O(N+G)\). Ý tưởng cơ bản là chia chiếc bánh thành các hình thang và duyệt từ trái sang phải để tích lũy tổng diện tích. Bất cứ khi nào một hình thang cần được chia cho một nhát cắt, một phương trình bậc hai sẽ được sử dụng để xác định vị trí cắt bánh. Cách tiếp cận này chỉ yêu cầu công thức cơ bản cho diện tích hình thang là \((a+b)/2 \times h\), trong đó \(a\) và \(b\) là độ dài hai đáy, và \(h\) là chiều cao của hình thang.

Thông tin thêm

• Diện tích đa giác (Polygon area)
• Tìm kiếm nhị phân (Binary search)

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