Bàn bi-a tự chế
Đề bài
Mô tả
Trí là một cậu bé rất mê chơi bi-a. Ước mơ của Trí là trở thành nhà vô địch quốc tế như Bao Phương Vinh, nhưng vì không có tiền đến câu lạc bộ bi-a để tập luyện, cậu quyết định tự làm một chiếc bàn bi-a để luyện tập.
Đáng tiếc là tay nghề làm bàn của Trí còn hạn chế, nên chiếc bàn cậu làm ra không đạt chuẩn quốc tế. Nhược điểm của chiếc bàn thì kể không xuể, nhưng chủ yếu là:
- Mặt bàn có thể không phải hình chữ nhật, nhưng chắc chắn là một tứ giác lồi.
- Mỗi lần bóng va vào thành bàn, vận tốc của bóng sau va chạm chỉ còn một nửa vận tốc trước va chạm.
Tuy vậy, chiếc bàn của Trí vẫn có các tính chất của một bàn bi-a. Khi bóng va vào thành bàn, nó bật lại như tia sáng phản xạ trên gương phẳng. Mọi điểm trên mặt bàn có cùng hệ số ma sát, tức là bóng luôn chuyển động chậm dần đều khi lăn trên mặt bàn với gia tốc hãm cm/s.
Để chứng minh chiếc bàn vẫn dùng được, Trí đặt một quả bóng đỏ và một vạch đánh dấu hình tròn màu trắng lên bàn. Bóng đỏ và vạch trắng cùng có bán kính cm, tâm lần lượt ở tọa độ và . Ban đầu bóng và vạch không chạm nhau và cách thành bàn ít nhất cm. Sau đó, Trí dùng gậy cơ tạo cho bóng đỏ một vận tốc ban đầu sao cho khi dừng lại, bóng đỏ nằm khít đúng vị trí vạch đánh dấu (tâm bóng trùng tâm vạch). Vì không phải tay cơ chuyên nghiệp, Trí không thể tạo vận tốc ban đầu lớn hơn cm/s. Tuy vậy, cậu muốn che đi nhược điểm nói trên, nên cố gắng cho bóng đỏ va vào thành bàn nhiều lần nhất có thể trước khi chạm vạch trắng. Bóng và vạch được gọi là chạm nhau nếu khoảng cách giữa hai tâm nhỏ hơn hoặc bằng tổng hai bán kính.
Bóng là một hình tròn bán kính , nên nó va vào một thành bàn khi tâm bóng cách đường thẳng chứa thành đó đúng cm. Hỏi Trí có thể tạo ra nhiều nhất bao nhiêu vị trí bóng đỏ va vào thành bàn trước khi tới vị trí vạch trắng?
Dữ liệu vào
- Dòng đầu tiên chứa tọa độ nguyên của đỉnh liên tiếp của bàn bi-a (đơn vị cm), với .
- Dòng thứ hai chứa số nguyên: tọa độ tâm bóng đỏ , tọa độ tâm vạch trắng và bán kính (cm) của chúng. Bóng đỏ và vạch trắng luôn nằm trong bàn và cách thành bàn ít nhất cm, .
- Dòng thứ ba chứa hai số thực: gia tốc hãm (cm/s) của bóng trên mặt bàn và vận tốc ban đầu tối đa (cm/s) của bóng đỏ, với và .
Dữ liệu ra
- Dòng đầu tiên in một số nguyên : số vị trí nhiều nhất mà bóng đỏ va vào thành bàn trước khi tới vị trí vạch trắng mà không chạm vạch trắng trước đó. Nếu không thể đưa bóng đỏ tới vị trí vạch trắng sau ít nhất một lần va vào thành bàn, in ra .
- dòng tiếp theo, mỗi dòng gồm số thực và số nguyên : tọa độ tâm bóng đỏ khi va vào thành bàn, và thành bàn đó là đoạn nối đỉnh với đỉnh của bàn. Các dòng được in theo thứ tự va chạm. Sai số tuyệt đối cho phép là . Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
- , bốn đỉnh tạo thành tứ giác lồi
- ; bóng đỏ và vạch trắng nằm trong bàn, cách thành bàn ít nhất cm và không chạm nhau
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 0 0 0 8 8 8 8 0 4 2 4 6 1 1.0 1000.0 |
3 2.0 1.0 4 1 1.0 1.5 1 2 7.0 4.5 3 4 |
Bàn là hình vuông cạnh . Bóng đỏ đi từ , va vào thành nối đỉnh , tại , thành nối đỉnh , tại , thành nối đỉnh , tại rồi dừng ở . |
| 3 11 14 15 14 1 1 1 7 5 11 6 2 2.0 500.0 |
2 4.554961773 3.0 3 4 3.596421722 3.784069582 4 1 |
Bóng đỏ va vào thành nối đỉnh , rồi thành nối đỉnh , trước khi dừng ở . |
Bình luận