trang chủ / đề bài / icpc22_reg_e

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 n đỉ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 H là hình chiếu của trọng tâm xúc xắc xuống mặt đất:

  • Nếu H nằm trên một cạnh của xúc xắc thì xúc xắc ổn định.
  • Nếu H 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 H 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 n đỉ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à (x1,y1),(x2,y2),…,(xn,yn) thì trọng tâm (Cx,Cy) của xúc xắc được tính theo công thức:

Cx=16A∑i=1n(xi+x(imodn)+1)(xiy(imodn)+1−x(imodn)+1yi)

Cy=16A∑i=1n(yi+y(imodn)+1)(xiy(imodn)+1−x(imodn)+1yi)

trong đó A là diện tích có dấu của đa giác:

A=12∑i=1n(xiy(imodn)+1−x(imodn)+1yi)

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n (3≤n≤105) là số đỉnh của xúc xắc.

Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên xi và yi (−109≤xi,yi≤109) là tọa độ đỉnh thứ i 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 n dòng. Dòng thứ i chứa xác suất cạnh thứ i là cạnh tiếp đất. Cạnh thứ i là cạnh nối đỉnh thứ i và đỉnh thứ (imodn)+1 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á 10−4. Cụ thể, gọi đáp án của bạn là a và đáp án của ban giám khảo là b, đáp án được chấp nhận khi và chỉ khi |a−b|max(1,|b|)≤10−4.

Ràng buộc

  • 3≤n≤105
  • −109≤xi,yi≤109
  • Đ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 1 là đáy dưới dài 10 từ (0,0) tới (10,0), cạnh 3 là đáy trên dài 8 từ (9,1) tới (1,1), cạnh 2 và cạnh 4 là hai cạnh bên ngắn. Cạnh 3 có xác suất tiếp đất lớn nhất: khi xúc xắc rơi với cạnh 2 hoặc cạnh 4 ở phía dưới, nó sẽ lăn sang cạnh 3. Vì vậy cạnh 2 và cạnh 4 có xác suất tiếp đất bằng 0.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0