trang chủ / đề bài / icpcwf16_g

Dầu mỏ

Đề bài

Mô tả

Một phần lớn nền kinh tế thế giới phụ thuộc vào dầu mỏ, vì vậy việc nghiên cứu các phương pháp mới để tìm kiếm và khai thác dầu vẫn đang rất sôi động. Lợi nhuận của các công ty dầu khí phụ thuộc một phần vào việc họ khoan dầu hiệu quả đến đâu. Tập đoàn Dầu thô Quốc tế (ICPC) hy vọng rằng các mô phỏng máy tính quy mô lớn sẽ giúp xác định cách khoan giếng dầu tốt nhất dễ dàng hơn.

Khoan giếng dầu tối ưu ngày càng khó: các mỏ dầu mới phát hiện thường không tạo thành một khối duy nhất mà bị chia thành nhiều phần. ICPC hiện quan tâm tới các mỏ dạng phân tầng, như minh họa ở hình dưới.

Hình: các lớp dầu nằm dưới mặt đất (Surface là mặt đất, trục y hướng xuống theo độ sâu). Hình ứng với ví dụ thứ nhất.

Để đơn giản, ICPC chỉ xét trường hợp hai chiều, trong đó các mỏ dầu được mô hình hóa thành các đoạn thẳng nằm ngang, song song với mặt đất. ICPC muốn biết nên đặt một giếng dầu duy nhất như thế nào để khai thác được nhiều dầu nhất. Giếng dầu được khoan từ mặt đất theo một đường thẳng và khai thác dầu từ mọi mỏ mà nó cắt trên đường đi xuống, kể cả khi giao điểm là một đầu mút của mỏ. Hình trên vẽ một giếng như vậy bằng nét đứt, đi qua ba mỏ. Trong mô hình đơn giản này, lượng dầu trong một mỏ bằng chiều rộng của mỏ đó. Hãy giúp ICPC xác định lượng dầu lớn nhất có thể khai thác bằng một giếng dầu duy nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n, số mỏ dầu.

Mỗi dòng trong n dòng tiếp theo mô tả một mỏ gồm ba số nguyên x0, x1 và y: mỏ là đoạn thẳng có hai đầu mút (x0,y) và (x1,y).

Dữ liệu ra

In ra lượng dầu lớn nhất có thể khai thác bằng một giếng dầu duy nhất.

Ràng buộc

  • 1≤n≤2000.
  • |x0|,|x1|≤106, 1≤y≤106.
  • Không có hai mỏ nào giao nhau, kể cả tại một điểm.

Ví dụ

Input Output Giải thích
5
100 180 20
30 60 30
70 110 40
10 40 50
0 80 70
200 Đây là hình trên. Giếng nét đứt đi qua các mỏ ở độ sâu 20, 40 và 70, khai thác 80+40+80=200.
3
50 60 10
-42 -42 20
25 0 10
25 Mỏ thứ ba có x0>x1, chiều rộng 25. Hai mỏ ở cùng độ sâu 10 không thể cùng bị một giếng cắt, mỏ ở độ sâu 20 có chiều rộ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