Hoạt động tuyệt vời
Đề bài
Mô tả
Alob và Bice là bạn thân nhiều năm và cuối cùng đã trở thành một cặp! Hôm nay là ngày 14 tháng 2, ngày lễ Tình nhân. Để kỷ niệm ngày này thật lãng mạn, cặp đôi quyết định dành cả ngày cho... một trò chơi với các điểm.
Đầu trò chơi, hai người chọn năm số nguyên dương , , , và . Sau đó họ vẽ điểm lên giấy, ký hiệu là . Coi tờ giấy là mặt phẳng tọa độ, tọa độ các điểm là , , , , . Nói cách khác, với mọi thỏa mãn , .
Luật chơi như sau:
- Hai người chơi lần lượt thay phiên nhau, Alob đi trước.
- Ở mỗi lượt, người chơi chọn hai điểm và () và vẽ đoạn thẳng .
- Sau mỗi lượt, điều kiện sau phải được thỏa mãn: không có hai đoạn thẳng đã vẽ nào giao nhau, kể cả tại đầu mút. Nói cách khác, mỗi điểm trên mặt phẳng thuộc không quá một đoạn thẳng.
Đọc tới đây, có thể bạn nghĩ người không thể đi một nước hợp lệ sẽ thua. Nhưng không! Họ đang yêu nhau nên rất ghét đối đầu. Thay vào đó, họ hợp tác với nhau để tạo ra càng nhiều hình vẽ khác nhau càng tốt!
Cụ thể, một hình vẽ là một tập (có thể rỗng) các đoạn thẳng có các đầu mút đều thuộc điểm , sao cho không có hai đoạn thẳng nào giao nhau. Không được phép giao nhau tại đầu mút. Quãng đường phủ của một hình vẽ là tổng độ dài mọi đoạn thẳng của nó. Hai hình vẽ được coi là khác nhau khi và chỉ khi có một đoạn thẳng xuất hiện trong hình vẽ này nhưng không xuất hiện trong hình vẽ kia. Lưu ý rằng hình vẽ không có đoạn thẳng nào luôn hợp lệ.
Cặp đôi muốn biết quãng đường phủ trung bình của tất cả các hình vẽ, được tính bằng tổng quãng đường phủ của mọi hình vẽ hợp lệ chia cho số hình vẽ hợp lệ.
Bạn hãy giúp họ nhé!
Nhắc lại rằng độ dài đoạn thẳng bằng khoảng cách Euclid giữa hai đầu mút và , được tính bằng , trong đó và lần lượt là tọa độ của hai điểm và .
Dữ liệu vào
Một dòng duy nhất chứa năm số nguyên , , , và . Mọi số đều nằm trong khoảng từ tới .
Dữ liệu ra
In ra một số thực là quãng đường phủ trung bình của tất cả các hình vẽ. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá . Cụ thể, gọi đáp án của bạn là và đáp án của ban giám khảo là , đáp án được chấp nhận khi và chỉ khi .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 2 1 1 | 2.82842712 | Có điểm , , , , và hình vẽ hợp lệ: hình vẽ rỗng; hình vẽ gồm một đoạn dài (, , , ); hình vẽ gồm một đoạn dài (, , ); hình vẽ gồm một đoạn dài (, ); hình vẽ gồm đoạn dài ; hình vẽ gồm hai đoạn dài (, , ); hình vẽ gồm một đoạn dài và một đoạn dài (, ). Quãng đường phủ trung bình là . |
| 2 7 9 3 4 | 5.0000000000 | Ví dụ bổ sung. Ba điểm cách đều nhau đơn vị. Có hình vẽ: rỗng, (dài ), (dài ), (dài ). Trung bình là . |
Bình luận