Phân tích: Watering Plants

Bài toán này liên quan đến việc tìm các hình tròn bao quanh các hình tròn khác. Bài toán tìm một hình tròn bao quanh một tập hợp các điểm là bài toán hình tròn bao tối tiểu (minimal enclosing circle) khá nổi tiếng, nhưng việc thay đổi các điểm thành các hình tròn làm cho bài toán trở nên khó léo hơn một chút.

Một giải pháp là sử dụng tìm kiếm nhị phân để tìm bán kính vòi phun tối thiểu. Điều này đưa bài toán về việc xác định xem hai vòi phun có bán kính \(R\) cho trước có thể bao phủ tất cả các cây hay không. Để giải quyết vấn đề này, chúng ta có thể đưa ra giả định rằng bất kỳ vòi phun nào được sử dụng trong giải pháp sẽ:

• Bao phủ chính xác một cây, hoặc
• Biên của vòi phun chạm vào biên của ít nhất hai cây mà nó bao phủ.

Giả định này là an toàn vì nếu một vòi phun bao phủ nhiều hơn một cây nhưng không có hai cây nào nằm trên biên của nó, vòi phun đó có thể được dịch chuyển và xoay trong khi vẫn bao phủ các cây đó, cho đến khi nó chạm biên. Dựa trên giả định này, chúng ta có thể tạo ra một tập hợp các vị trí vòi phun ứng viên bao gồm:

• Một vòi phun có tâm tại mỗi cây (bán kính \(R - r_i\) nếu \(R \ge r_i\)).
• Đối với mỗi cặp cây, tập hợp các vòi phun bao phủ hai cây đó và chạm vào biên của chúng (có 0, 1 hoặc 2 vị trí như vậy cho mỗi cặp).

Sau đó, chúng ta kiểm tra mọi cặp vòi phun ứng viên và xem có cặp nào cùng nhau bao phủ được tất cả các cây hay không.

Giải pháp thứ hai là trực tiếp tìm bán kính vòi phun tối thiểu. Để thực hiện việc này, chúng ta có thể sử dụng một giả định đơn giản hóa hơi khác một chút -- rằng mỗi vòi phun sẽ:

• Bao phủ chính xác một cây (sử dụng cùng bán kính với cây đó),
• Bao phủ hai cây chạm vào cạnh của vòi phun và tâm của chúng thẳng hàng với tâm của vòi phun, hoặc
• Bao phủ ba cây chạm vào cạnh của vòi phun.

Giả định này an toàn vì bất kỳ vòi phun nào khác đều có thể được thu nhỏ lại thành một vòi phun có bán kính nhỏ hơn mà vẫn bao phủ cùng một tập hợp các cây. Chúng ta thử từng tập hợp các cây có kích thước 1, 2 hoặc 3, tạo vòi phun tương ứng từ ba trường hợp trên, kiểm tra bán kính của nó và tập hợp các cây mà nó bao phủ. Sau đó, chúng ta tìm cặp vòi phun bao phủ mọi cây với giá trị cực đại của hai bán kính là nhỏ nhất.

Việc tìm hình tròn tiếp xúc với 3 hình tròn cho trước (bài toán Apollonius) khó hơn bài toán tương đương với 3 điểm. Dưới đây là ba cách tiếp cận khả thi:

1. Tập hợp các điểm mà tâm vòi phun có thể đặt để tiếp xúc với hai cây là một đường hyperbol, vì vậy chúng ta có thể tính toán đại số giao điểm của hai đường hyperbol đó.
2. Chúng ta có thể sử dụng phương pháp gradient-descent để tìm bằng số điểm cực tiểu hóa hàm số từ các tâm vòi phun tiềm năng đến bán kính cần thiết để một vòi phun đặt tại vị trí đó bao phủ cả ba cây.
3. Chúng ta có thể trừ bán kính của cây nhỏ nhất khỏi bán kính của cả ba cây (đưa một cây về một điểm), sau đó thực hiện phép nghịch đảo qua tâm của điểm đó. Tiếp theo, tìm các tiếp tuyến thích hợp cho hai hình tròn đã nghịch đảo, nghịch đảo ngược lại để tìm hình tròn tương ứng, và cộng lại bán kính của cây nhỏ nhất.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 2 - Watering Plants, thuộc kho Google Coding Competitions (Apache-2.0).