3. Google Code Jam 2010 - Grazing Google Goats
Nông dân John vừa mới mua một đàn gồm \(N\) con dê cho cánh đồng của mình. Mỗi con dê \(i\) sẽ được buộc vào một chiếc cọc tại vị trí \(P_i\) bằng một sợi dây thừng có độ dài \(L_i\). Điều này có nghĩa là con dê có thể di chuyển đến bất cứ đâu trên cánh đồng trong khoảng cách \(L_i\) tính từ điểm \(P_i\), nhưng không thể đi xa hơn. (Cánh đồng rất lớn và phẳng, vì vậy bạn có thể coi nó như một mặt phẳng hai chiều vô hạn.)
Nông dân John đã chọn sẵn các vị trí đặt cọc từ đàn dê trước, nhưng ông ấy phải chọn độ dài dây thừng. Có hai yếu tố khiến quyết định này trở nên khó khăn:
- Tất cả các con dê đều cần có khả năng tiếp cận một máng nước duy nhất. Nông dân John vẫn chưa quyết định đặt máng nước này ở đâu. Ông đã thu hẹp lựa chọn xuống một tập hợp các vị trí \(\{Q_1, Q_2, \dots, Q_M\}\), nhưng ông không chắc nên sử dụng vị trí nào.
- Những con dê này rất nóng tính, và khi chúng tụ tập lại với nhau, đôi khi chúng xảy ra những cuộc ẩu đả ồn ào. Để mọi người được yên tĩnh, Nông dân John muốn giảm thiểu diện tích \(A\) mà tất cả các con dê đều có thể tiếp cận được.
Thật không may, Nông dân John không giỏi hình học, và ông ấy cần sự giúp đỡ của bạn!
Với mỗi vị trí máng nước \(Q_j\), bạn nên chọn độ dài các sợi dây thừng sao cho tối thiểu hóa diện tích \(A_j\) mà mọi con dê đều có thể tiếp cận được khi máng nước đặt tại vị trí \(Q_j\). Sau đó, bạn hãy tính toán từng diện tích \(A_j\) này.
Ví dụ
Trong hình dưới đây, có bốn điểm màu xanh lam tương ứng với các vị trí cọc: \(P_1, P_2, P_3\), và \(P_4\). Ngoài ra còn có hai điểm màu đỏ tương ứng với các vị trí máng nước tiềm năng: \(Q_1\) và \(Q_2\). Bạn cần tính \(A_1\) và \(A_2\), diện tích của hai vùng được tô bóng.
Dữ liệu vào
Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). Tiếp theo là \(T\) bộ thử nghiệm. Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa các số nguyên \(N\) và \(M\).
\(N\) dòng tiếp theo chứa các vị trí \(P_1, P_2, \dots, P_N\), mỗi vị trí trên một dòng. Tiếp theo là \(M\) dòng chứa các vị trí \(Q_1, Q_2, \dots, Q_M\), mỗi vị trí trên một dòng.
Mỗi dòng trong số \(N + M\) dòng này chứa tọa độ \(x\) và \(y\) tương ứng của vị trí đó, cách nhau bởi một khoảng trắng.
Dữ liệu ra
Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: \(A_1\) \(A_2\) ... \(A_M\)", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và \(A_1\) \(A_2\) ... \(A_M\) là các giá trị diện tích đã định nghĩa ở trên. Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-6}\) sẽ được coi là chính xác.
Ràng buộc
- Tất cả các tọa độ là số nguyên trong khoảng từ -10,000 đến 10,000.
- Các vị trí \(P_1, P_2, \dots, P_N, Q_1, Q_2, \dots, Q_M\) đều phân biệt và không có ba điểm nào thẳng hàng.
Phân nhóm
-
Thông số Test 1 (Visible):
- \(1 \le T \le 100\).
- \(N = 2\).
- \(1 \le M \le 10\).
-
Thông số Test 2 (Hidden):
-
\(1 \le T \le 10\).
- \(2 \le N \le 5,000\).
- \(1 \le M \le 1,000\).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 7/32 | 21,88% |
| Test Set 2 | 25/32 | 78,12% |
Ví dụ
Ví dụ 1
Input
3
2 3
0 20
20 0
-20 10
40 20
0 19
4 2
0 0
100 100
300 0
380 90
400 100
1000 5
3 1
0 0
10 10
20 0
10 5Output
Case #1: 1264.9865911 1713.2741229 0.2939440
Case #2: 1518.9063729 1193932.9692206
Case #3: 0.0Nguồn
Google Code Jam 2010, Vòng 2, bài Grazing Google Goats.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
