trang chủ / đề bài / icpc26_mn_l

Nỗi buồn

Đề bài

Mô tả

Chúc mừng Doggie!

(Demen)

Doggie làm việc với các hỗn hợp lỏng gồm Thủy ngân (Hg) và Tacos (Ts). Một hỗn hợp được biểu diễn bởi cặp (x,y) chứa x gam Hg và y gam Ts.

Doggie đang có sẵn n hỗn hợp. Anh ấy cũng có thể mua thêm một số lượng hữu hạn bất kỳ các hỗn hợp mới. Mua một hỗn hợp chứa x gam Hg và y gam Ts tốn chi phí ax+by, trong đó x và y có thể là các số thực không âm bất kỳ. Trong phần dưới đây, hỗn hợp thứ i (có sẵn hoặc mua thêm) chứa xi gam Hg và yi gam Ts.

Để tạo ra một hỗn hợp, Doggie lấy một tỉ lệ pi∈[0,1] một cách độc lập từ mỗi hỗn hợp mà anh ấy sở hữu, dù là hỗn hợp có sẵn hay hỗn hợp mua thêm. Các tỉ lệ không cần có tổng bằng 1. Kết quả chứa đúng ∑ipixi gam Hg và ∑ipiyi gam Ts.

Doggie đang cân nhắc m hỗn hợp mục tiêu có thể dùng cho thí nghiệm của mình, nhưng anh ấy chưa quyết định sẽ tạo ra hỗn hợp nào. Trong giai đoạn thí nghiệm sau này, cửa hàng sẽ không còn hỗn hợp nào để bán, nên anh ấy không thể mua thêm. Anh ấy muốn mua đủ ngay bây giờ để đảm bảo có thể tạo ra bất kỳ mục tiêu nào mà mình chọn sau này. Anh ấy sẽ chỉ tạo ra một mục tiêu, và có thể chọn các tỉ lệ sau khi đã quyết định tạo mục tiêu nào. Kết quả phải chứa đúng lượng Hg và lượng Ts của mục tiêu đó.

Hãy giúp Doggie chọn các hỗn hợp cần mua sao cho mọi mục tiêu đều có thể được tạo ra, đồng thời tổng chi phí của các hỗn hợp mua thêm là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên n, m, a và b (1≤n,m≤436879; 1≤a,b≤396).

Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên xi và yi (0≤xi,yi≤436879): số gam Hg và Ts trong một hỗn hợp có sẵn.

Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên Xj và Yj (0≤Xj,Yj≤436879): số gam Hg và Ts trong một hỗn hợp mục tiêu.

Dữ liệu ra

In ra một số thực: tổng chi phí nhỏ nhất để mua các hỗn hợp mới.

Đáp án của bạn được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−6. Cụ thể, gọi đáp án của bạn là u và đáp án của ban giám khảo là v; đáp án được chấp nhận khi và chỉ khi |u−v|max(1,|v|)≤10−6.

Ràng buộc

  • 1≤n,m≤436879.
  • 1≤a,b≤396.
  • 0≤xi,yi≤436879.
  • 0≤Xj,Yj≤436879.

Ví dụ

Input Output Giải thích
5 2 1 1
1 2
3 4
5 6
7 8
9 10
80 80
100 100
145.000000000000 Năm hỗn hợp có sẵn chứa tổng cộng 25 gam Hg và 30 gam Ts. Nếu sau này Doggie chọn mục tiêu chứa 100 gam mỗi chất, anh ấy cần thêm ít nhất 75 gam Hg và 70 gam Ts, nên phải tốn ít nhất 145. Doggie có thể mua một hỗn hợp chứa đúng 75 gam Hg và 70 gam Ts. Nếu chọn mục tiêu (100,100), anh ấy dùng toàn bộ sáu hỗn hợp; nếu chọn mục tiêu (80,80), anh ấy dùng 80% của mỗi hỗn hợp. Vậy đáp án là 145.
3 3 3 1
6 4
0 0
0 2
2 1
1 3
4 5
1.833333333333 Đáp án là 116.

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