trang chủ / đề bài / icpc22_reg_f

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 n, x0, y0, a và b. Sau đó họ vẽ n+1 điểm lên giấy, ký hiệu là P0,P1,…,Pn. Coi tờ giấy là mặt phẳng tọa độ, tọa độ các điểm là P0=(x0,y0), P1=(x0+a,y0+b), P2=(x0+2·a,y0+2·b), …, Pn=(x0+n·a,y0+n·b). Nói cách khác, với mọi i thỏa mãn 0≤i≤n, Pi=(x0+i·a,y0+i·b).

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 Pi và Pj (0≤i<j≤n) và vẽ đoạn thẳng PiPj.
  • 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 n+1 điểm P0,P1,…,Pn, 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 PiPj 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 AB bằng khoảng cách Euclid giữa hai đầu mút A và B, được tính bằng (xA−xB)2+(yA−yB)2, trong đó (xA,yA) và (xB,yB) lần lượt là tọa độ của hai điểm A và B.

Dữ liệu vào

Một dòng duy nhất chứa năm số nguyên n, x0, y0, a và b. Mọi số đều nằm trong khoảng từ 1 tới 100000.

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á 10−6. 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−6.

Ràng buộc

  • 1≤n,x0,y0,a,b≤100000

Ví dụ

Input Output Giải thích
4 2 2 1 1 2.82842712 Có 5 điểm P0=(2,2), P1=(3,3), P2=(4,4), P3=(5,5), P4=(6,6) và 16 hình vẽ hợp lệ: 1 hình vẽ rỗng; 4 hình vẽ gồm một đoạn dài 2 (P0P1, P1P2, P2P3, P3P4); 3 hình vẽ gồm một đoạn dài 8 (P0P2, P1P3, P2P4); 2 hình vẽ gồm một đoạn dài 18 (P0P3, P1P4); 1 hình vẽ gồm đoạn P0P4 dài 32; 3 hình vẽ gồm hai đoạn dài 2 ({P0P1,P2P3}, {P0P1,P3P4}, {P1P2,P3P4}); 2 hình vẽ gồm một đoạn dài 2 và một đoạn dài 8 ({P0P1,P2P4}, {P0P2,P3P4}). Quãng đường phủ trung bình là 42+38+218+32+3·22+2(2+8)16≈2.82842712.
2 7 9 3 4 5.0000000000 Ví dụ bổ sung. Ba điểm cách đều nhau 5 đơn vị. Có 4 hình vẽ: rỗng, P0P1 (dài 5), P1P2 (dài 5), P0P2 (dài 10). Trung bình là 0+5+5+104=5.

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