1. Google Code Jam 2008 - Fly Swatter
Khả năng bạn đánh trúng một con ruồi bằng vợt tennis là bao nhiêu?
Để bắt đầu, hãy bỏ qua cán vợt. Giả sử mặt vợt là một vòng tròn hoàn hảo, có bán kính ngoài là \(R\) và độ dày là \(t\) (vì vậy bán kính trong của vòng tròn là \(R - t\)).
Mặt vợt được bao phủ bởi các dây ngang và dọc. Mỗi sợi dây là một hình trụ có bán kính \(r\). Mỗi sợi dây là một dây cung của vòng tròn (một đoạn thẳng nối hai điểm của đường tròn). Có một khoảng trống độ dài \(g\) giữa các dây lân cận. Các dây đối xứng qua tâm của vợt, tức là có một cặp dây mà tâm của chúng giao nhau tại tâm của vòng tròn.
Con ruồi là một hình cầu bán kính \(f\). Giả sử rằng vợt đang di chuyển theo một đường thẳng vuông góc với mặt phẳng của vòng tròn. Giả sử tâm của con ruồi nằm bên trong bán kính ngoài của vợt và có khả năng nằm ở bất kỳ đâu trong bán kính đó với xác suất như nhau. Bất kỳ sự giao thoa nào giữa con ruồi và vợt (vòng tròn hoặc dây) đều được tính là một cú đánh trúng.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên \(N\), số lượng bộ thử nghiệm trong tệp đầu vào.
\(N\) dòng tiếp theo, mỗi dòng chứa các số \(f\), \(R\), \(t\), \(r\) và \(g\) cách nhau bởi đúng một khoảng trắng. Các số này sẽ có chính xác 6 chữ số sau dấu phẩy thập phân.
Dữ liệu ra
\(N\) dòng, mỗi dòng có dạng Case #k: P, trong đó \(k\) là số thứ tự của bộ thử nghiệm và \(P\) là xác suất đánh trúng con ruồi bằng một phần của chiếc vợt.
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
- \(f, R, t, r\) và \(g\) là các số dương và nhỏ hơn hoặc bằng \(10000\).
- \(t < R\)
- \(f < R\)
- \(r < R\)
Phân nhóm
- Small dataset (Test set 1): \(1 \le N \le 30\). Tổng số dây tối đa là 60 (tối đa 30 dây mỗi hướng).
- Large dataset (Test set 2): \(1 \le N \le 100\). Tổng số dây tối đa là 2000 (tối đa 1000 dây mỗi hướng).
Đ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 | 5/25 | 20% |
| Test Set 2 | 20/25 | 80% |
Ví dụ
Ví dụ 1
Input
5
0.250000 1.000000 0.100000 0.010000 0.500000
0.250000 1.000000 0.100000 0.010000 0.900000
0.000010 10000.000000 0.000010 0.000010 1000.000000
0.400000 10000.000000 0.000010 0.000010 700.000000
1.000000 100.000000 1.000000 1.000000 10.000000Output
Case #1: 1.000000
Case #2: 0.910015
Case #3: 0.000000
Case #4: 0.002371
Case #5: 0.573972Nguồn
Google Code Jam 2008, Vòng loại, bài Fly Swatter.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.