Phân tích: Grazing Google Goats

Bài này khó cả về cài đặt lẫn thuật toán. Trước hết, ta sẽ trình bày một số khái niệm tổng quát cho thấy bài toán thực ra rất giống bao lồi; sau đó đi vào các chi tiết cần thiết để xây dựng lời giải và chứng minh tính đúng đắn. Mã nguồn thu được không đáng sợ như độ dài của phần phân tích.

Chỉ xét từng máng nước \(Q\). Ta phải chọn độ dài dây, tức là với mỗi vị trí cọc phải chọn bán kính đường tròn tâm tại cọc đó. Miền chung là giao của tất cả các hình tròn. Giảm bán kính bất kỳ không thể làm giao lớn hơn, nên ta muốn dây ngắn nhất có thể. Với mỗi cọc \(P_i\), rõ ràng \(P_iQ\) là độ dài nhỏ nhất vẫn cho phép dê chạm tới máng. Nhiệm vụ chính là tính hiệu quả diện tích giao của các hình tròn này.

Theo giới hạn, tính giao trong thời gian \(\Omega(N^2)\) là quá chậm. Mục tiêu là thuật toán \(O(N\log N)\) cho mỗi máng.

Giao là một hình lồi, biên gồm các cung tròn. Có thể chứng minh theo nhiều cách — một phần lý do sẽ rõ ở dưới — rằng mỗi đường tròn đóng góp nhiều nhất một cung. Ta chủ yếu cần tìm các cung này: thuộc đường tròn nào, bắt đầu và kết thúc ở đâu. Khi có đủ thông tin đó, tính diện tích tương đối dễ.

Một số cơ sở lý thuyết

Phần này không tuyệt đối cần thiết để giải bài, nhưng đem lại trực giác hữu ích. Nhìn bài toán từ vài góc độ sẽ khiến lời giải trở nên rõ ràng và tự nhiên.

Mọi đường tròn đang xét đều đi qua điểm chung \(Q\). Ta dùng phép biến đổi hình học đẹp gọi là nghịch đảo, lấy \(Q\) làm tâm. Mỗi điểm \(X\ne Q\) được ánh xạ thành \(X'\) sao cho \(QX\) và \(QX'\) cùng hướng và

Một tính chất quan trọng: mọi đường tròn đi qua tâm nghịch đảo \(Q\) được ánh xạ thành một đường thẳng không đi qua \(Q\), và ngược lại. Phần trong đường tròn được ánh xạ thành một nửa mặt phẳng không chứa \(Q\). Vì vậy, giao của \(N\) hình tròn trong bài được ánh xạ thành giao của \(N\) nửa mặt phẳng. Có thể xem thêm trang Wikipedia về hình học nghịch đảo.

Bạn đọc có thể kiểm tra rằng nếu giao không rỗng, ta có thể xoay mặt phẳng để \(Q\) nằm phía trên mọi nửa mặt phẳng. Khi đó, giao các nửa mặt phẳng được giới hạn bởi thứ gọi là bao dưới của một sắp xếp đường thẳng. Các đoạn của bao dưới chính xác là ảnh của các cung trên biên giao hình tròn ban đầu.

Trong hình học tính toán còn có khái niệm đối ngẫu, ánh xạ mỗi đường thẳng y=ax+b thành điểm (a,-b). Qua phép biến đổi này, bao dưới được ánh xạ thành bao lồi trên của tập điểm tương ứng.

Như vậy, bài toán tương đương với bài toán bao lồi và bài toán bao dưới của sắp xếp đường thẳng. Cả hai đều đã được nghiên cứu kỹ và có thuật toán \(O(N\log N)\) đơn giản.

Trong ba cách nhìn, thuật toán cho sắp xếp đường thẳng có lẽ dễ hình dung nhất: sắp các đường theo hệ số góc rồi thêm từng đường. Ở mỗi bước, đường mới cắt bao dưới hiện có thành hai phần. Sắp xếp mất \(O(N\log N)\); phần còn lại có độ phức tạp khấu hao \(O(N)\).

Lời giải trực tiếp

Phần trước gợi ý vài cách bắt đầu bằng việc thực hiện tường minh phép nghịch đảo quanh \(Q\). Ở đây ta trình bày lời giải trực tiếp, không cần nhìn qua các phép biến đổi đó, dù về bản chất nó tương đương thuật toán sắp xếp đường thẳng nói trên.

Nhìn từ \(Q\) theo một tia thẳng. Giao của tia với mỗi hình tròn hoặc chỉ là \(Q\), hoặc là đoạn từ \(Q\) đến giao điểm thứ hai của tia với đường tròn. Do đó, để dựng miền cần tìm, ở mỗi hướng từ \(Q\) ta phải tìm đường tròn “gần” \(Q\) nhất. Biểu diễn mỗi hướng bằng góc cực, xác định theo modulo \(2\pi\).

Trước hết xét một đường tròn. Giả sử tia từ \(Q\) hướng về tâm có góc cực \(\varphi\). Khi góc tia tăng từ \(\varphi-\pi/2\) đến \(\varphi\), khoảng cách từ \(Q\) tới giao điểm thứ hai tăng từ \(0\) đến đường kính. Khi góc tiếp tục từ \(\varphi\) đến \(\varphi+\pi/2\), khoảng cách giảm về \(0\). Với góc từ \(\varphi+\pi/2\) đến \(\varphi+3\pi/2\) (điểm cuối đồng nhất với \(\varphi-\pi/2\)), tia chỉ giao hình tròn tại \(Q\).

Xét hai đường tròn có tâm ở góc cực lần lượt \(\varphi\) và \(\xi\), với \(0<\varphi-\xi<\pi\). Khi quay tia từ \(Q\):

• Từ \(\xi-\pi/2\) đến \(\varphi-\pi/2\), tia chỉ cắt đường tròn thứ hai.
• Từ \(\varphi-\pi/2\), tia cắt cả hai, nhưng giao điểm với đường tròn thứ nhất gần \(Q\) hơn cho đến hướng đi qua giao điểm của hai đường tròn.
• Sau hướng giao điểm và đến \(\xi+\pi/2\), tia vẫn cắt cả hai nhưng đường tròn thứ hai gần hơn.
• Từ \(\xi+\pi/2\) đến \(\varphi+\pi/2\), tia chỉ cắt đường tròn thứ nhất.

Điểm quan trọng là trong khoảng góc mà tia cắt cả hai — chính là khoảng ta quan tâm khi tìm diện tích giao — tình huống rất đơn giản: trước giao điểm, một đường tròn gần \(Q\) hơn; sau giao điểm, đường kia gần hơn.

Với nhiều đường tròn, trước hết tìm góc cực của từng tâm và khoảng góc mà tia từ \(Q\) cắt đường tròn đó. Giao tất cả các khoảng này để được một khoảng nhỏ \([\alpha,\beta]\) mà mọi tia đều cắt mọi đường tròn. Nếu khoảng rỗng thì giao hình tròn không có diện tích cần xét.

Thêm các đường tròn từng cái một, bắt đầu từ tâm có góc cực nhỏ nhất. “Nhỏ nhất” trên đường tròn góc nghĩa là gì? May thay, ở đây ta có ít hơn một vòng đầy đủ: vì mọi hình tròn đều cắt mọi tia trong \([\alpha,\beta]\), góc cực của các tâm nằm giữa \(\beta-\pi/2\) và \(\alpha+\pi/2\). Đây là một đoạn dài nhỏ hơn \(\pi\), nên có thứ tự xác định.

Trong quá trình thêm, duy trì đường tròn gần nhất với từng góc trong \([\alpha,\beta]\). Sau đường tròn đầu tiên, nó gần nhất trên toàn khoảng. Thêm đường tròn thứ hai và gọi góc cực của giao điểm hai đường tròn là \(\gamma\):

• Nếu \(\gamma<\alpha\), đường tròn thứ nhất vẫn gần nhất trên toàn \([\alpha,\beta]\).
• Nếu \(\alpha\le\gamma\le\beta\), đường tròn thứ hai gần nhất trên \([\alpha,\gamma]\), còn đường tròn thứ nhất gần nhất trên \([\gamma,\beta]\).
• Nếu \(\gamma>\beta\), đường tròn thứ hai gần nhất trên toàn \([\alpha,\beta]\).

Lập luận này dựa trên việc xử lý các đường tròn theo thứ tự tăng dần góc cực của tâm.

Xét trường hợp tổng quát. Trước khi thêm đường tròn \(i\), giả sử trên \([\alpha,\gamma_1]\) đường tròn \(j_1\) gần nhất; trên \([\gamma_1,\gamma_2]\) là \(j_2\); ...; và trên \([\gamma_{k-1},\beta]\) là \(j_k\).

Gọi \(\delta\) là góc cực của giao điểm giữa đường tròn \(i\) và \(j_1\). Có ba trường hợp so với khoảng mà \(j_1\) đang gần nhất:

• Nếu \(\delta<\alpha\), \(j_1\) gần hơn \(i\) trên toàn đoạn \([\alpha,\beta]\). Dừng xử lý \(i\) vì nó không ảnh hưởng đáp án.
• Nếu \(\alpha\le\delta\le\gamma_1\), giờ \(i\) gần nhất trên \([\alpha,\delta]\), còn \(j_1\) gần nhất trên \([\delta,\gamma_1]\). Sau thay đổi này cũng có thể dừng, vì \(j_1\) sẽ gần \(Q\) hơn trên toàn phần còn lại.
• Nếu \(\delta>\gamma_1\), bỏ \(j_1\) vì \(i\) gần hơn nó trên toàn \([\alpha,\gamma_1]\). Tiếp tục so sánh \(i\) với \(j_2\), rồi cứ thế.

Sau khi xử lý mọi đường tròn, ta biết đường bao của hình giao và có thể tính diện tích.

Thuật toán cần cấu trúc dữ liệu duy trì danh sách các cung kèm nhãn số nguyên, cho phép sửa cung đầu, xóa cung đầu và thêm cung đầu mới. Đơn giản nhất là dùng ngăn xếp: cung đầu ở đỉnh và cung cuối ở đáy.

Phân tích khấu hao: khi xử lý mỗi đường tròn, thực hiện nhiều nhất hai thao tác đẩy và một hoặc nhiều thao tác lấy khỏi ngăn xếp. Tổng số lần đẩy là \(O(N)\); tổng số lần lấy không thể vượt số lần đẩy, nên cũng là \(O(N)\). Phần này tổng cộng \(O(N)\). Tuy nhiên còn phải sắp xếp các đường tròn theo góc cực của tâm, nên toàn bộ thời gian là \(O(N\log N)\).

Ta chưa nói đến hai thủ tục hình học mức thấp cần thiết:

1. Tìm góc cực của giao điểm còn lại của hai đường tròn khi giao điểm thứ nhất là gốc tọa độ.
2. Tìm diện tích một hình có biên là các cung tròn.

Thủ tục thứ nhất đơn giản nếu đã biết cách tìm giao hai đường tròn; ngoài ra có thể suy ra trực tiếp công thức góc cực. Thủ tục thứ hai khó hơn đôi chút. Trước tiên, chia hình thành các “tam giác bo tròn” bằng những tia từ \(Q\) có góc cực \(\gamma_1,\gamma_2,\ldots,\gamma_{k-1}\). Mỗi tam giác bo tròn có hai cạnh thẳng (một cạnh có thể dài \(0\)) và một cạnh cung tròn. Chia nó thành tam giác tương ứng cộng phần cong bị cắt từ hình tròn. Diện tích tam giác có thể tính bằng công thức dây giày. Để tính phần cong, bắt đầu với một hình quạt từ tâm — diện tích là một tỉ lệ đơn giản của diện tích cả hình tròn — rồi cộng hoặc trừ diện tích các tam giác.

Quả thật có khá nhiều việc phải làm, nhưng đó là lý do đây là Bài số 4!

Nguồn

Bản dịch đầy đủ dựa trên phân tích chính thức của Google Code Jam 2010 - Grazing Google Goats, thuộc kho Google Coding Competitions (Apache-2.0).