Tổn thương tinh thần
Đề bài
Mô tả
Steven vừa được tặng một con xúc xắc nhân dịp sinh nhật! Cậu rất thích nó và thường dùng nó để chơi với bạn bè. Nhưng một ngày nọ, cậu không tìm thấy con xúc xắc ở đâu cả! Cậu nhờ bố giúp:
- Bố ơi, bố có thấy xúc xắc của con đâu không?
- Không, bố không thấy. Nhưng con có thể dùng con của bố. Đây!
Steven rất vui khi có xúc xắc của bố. Nhưng cậu nhanh chóng bối rối khi phát hiện ra xúc xắc của bố không bình thường. Con xúc xắc có thể xem như một đa giác lồi đỉnh trên mặt phẳng. Đa giác này thậm chí còn không đều, khiến Steven càng bối rối hơn.
- Bố ơi, sao các mặt của xúc xắc lại không giống nhau? Bố có chắc là chơi được với con xúc xắc này không?
- Nghe này con. Hồi bố còn nhỏ, xúc xắc còn chưa được phát minh. Hồi đi học, bố phải đi bộ 20 dặm. Lên dốc. Cả hai chiều. 26 tiếng một ngày. Bằng một chân. Chân còn lại thì lo tính toán xác suất! Con phải tự tìm hiểu thôi.
Vì vậy Steven cần biết con xúc xắc công bằng đến mức nào. Để làm được điều đó, với mỗi cạnh của xúc xắc, cậu muốn biết xác suất cạnh đó là cạnh tiếp đất khi tung xúc xắc.
Cụ thể, khi tung xúc xắc, xúc xắc được nhấc lên đủ cao so với mặt đất. Sau đó, ta chọn một góc ngẫu nhiên đều và xoay xúc xắc một góc quanh trọng tâm của nó. Cuối cùng, ta thả cho xúc xắc rơi.
Khi chạm đất, xúc xắc có thể ở trạng thái chưa ổn định. Xúc xắc sẽ tiếp tục lăn cho tới khi ổn định. Giả sử rằng:
- Xúc xắc có khối lượng phân bố đều, nên trọng tâm của nó là vị trí trung bình cộng của mọi điểm bên trong nó.
- Khối lượng của xúc xắc đủ lớn để không bị nảy lên khi chạm đất, và xúc xắc sẽ không lăn thêm khi đã ổn định.
- Mặt đất bằng phẳng.
Xét là hình chiếu của trọng tâm xúc xắc xuống mặt đất:
- Nếu nằm trên một cạnh của xúc xắc thì xúc xắc ổn định.
- Nếu nằm bên trái mọi điểm tiếp xúc của xúc xắc với mặt đất thì xúc xắc sẽ lăn sang trái.
- Nếu nằm bên phải mọi điểm tiếp xúc của xúc xắc với mặt đất thì xúc xắc sẽ lăn sang phải.
Cho đa giác đỉnh biểu diễn con xúc xắc, hãy giúp Steven tìm xem xúc xắc công bằng đến mức nào bằng cách tính xác suất mỗi cạnh của xúc xắc là cạnh tiếp đất.
Nếu các đỉnh của xúc xắc là thì trọng tâm của xúc xắc được tính theo công thức:
trong đó là diện tích có dấu của đa giác:
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên () là số đỉnh của xúc xắc.
Dòng thứ trong dòng tiếp theo chứa hai số nguyên và () là tọa độ đỉnh thứ của xúc xắc.
Dữ liệu đảm bảo:
- các đỉnh được liệt kê theo thứ tự ngược chiều kim đồng hồ,
- đa giác đã cho là đa giác lồi,
- không có ba đỉnh liên tiếp nào của đa giác thẳng hàng.
Dữ liệu ra
In ra dòng. Dòng thứ chứa xác suất cạnh thứ là cạnh tiếp đất. Cạnh thứ là cạnh nối đỉnh thứ và đỉnh thứ theo thứ tự trong dữ liệu vào.
Đá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
- Đa giác lồi, các đỉnh theo thứ tự ngược chiều kim đồng hồ, không có ba đỉnh liên tiếp thẳng hàng.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 0 0 1 0 1 1 0 1 |
0.25 0.25 0.25 0.25 |
Xúc xắc là hình vuông nên mọi cạnh có khả năng tiếp đất như nhau. |
| 4 0 0 10 0 9 1 1 1 |
0.46944215849887844 0 0.5305578415011215 0 |
Xúc xắc là hình thang: cạnh là đáy dưới dài từ tới , cạnh là đáy trên dài từ tới , cạnh và cạnh là hai cạnh bên ngắn. Cạnh có xác suất tiếp đất lớn nhất: khi xúc xắc rơi với cạnh hoặc cạnh ở phía dưới, nó sẽ lăn sang cạnh . Vì vậy cạnh và cạnh có xác suất tiếp đất bằng . |
Bình luận