Kênh ngầm qanat
Đề bài
Mô tả
Qanat là một hệ thống thủy lợi được dùng rộng rãi để dẫn nước ở những vùng khí hậu nóng và khô hạn. Kỹ thuật này do người Ba Tư phát triển từ hơn năm trước. Ở Maroc, qanat được gọi là khettara và đến nay vẫn còn được sử dụng ở miền nam nước này.
Thành phần cơ bản của một qanat là một kênh gần như nằm ngang, dẫn nước từ một nguồn nước ngầm tới một cửa ra gần khu dân cư. Ngoài ra còn có một giếng đứng gọi là giếng mẹ, đi thẳng từ nguồn nước ngầm lên tới mặt đất trên sườn núi hoặc đồi. Xây dựng một hệ thống như vậy cực kỳ tốn kém, nhất là vào thời xưa, vì toàn bộ đất đá đào ra từ kênh và giếng mẹ đều phải được mang lên mặt đất, qua cửa ra của kênh hoặc qua miệng giếng mẹ. Để hỗ trợ việc xây dựng, người ta thường đào thêm một hoặc nhiều giếng đứng ở những vị trí được chọn kỹ phía trên kênh ngầm. Các giếng này cũng phải được đào, nhưng chúng cho phép đưa thêm đất từ kênh ngang lên mặt đất.
Trong bài này, mặt cắt của qanat được mô hình hóa như sau: cửa ra của kênh ở điểm , nguồn nước ở điểm và miệng giếng mẹ ở điểm , với . Mặt sườn núi là đoạn thẳng nối với . Kênh ngầm là đoạn từ tới , giếng mẹ là đoạn thẳng đứng từ tới .
graph 3 1 2 2 3 3 1 pos 1 0 100 pos 2 360 100 pos 3 360 0 label 1 (0, 0) label 2 (w, 0) label 3 (w, h)
Mỗi qanat phải có giếng mẹ thẳng đứng từ nguồn nước lên tới mặt sườn núi, cùng với giếng đứng bổ sung. Kênh và mọi giếng đều được mô hình hóa là các đoạn thẳng. Nhiệm vụ của bạn là chọn vị trí cho các giếng bổ sung để tổng chi phí đào là nhỏ nhất. Chi phí này bằng tổng quãng đường mà mỗi phần đất đào ra phải được vận chuyển để lên tới mặt đất (có thể kết hợp tùy ý di chuyển theo phương ngang và phương thẳng đứng). Ví dụ, chi phí đào một đoạn đất liên tục bắt đầu từ mặt đất và đi theo một đường có độ dài (có thể có chỗ rẽ) là .
Dữ liệu vào
Một dòng duy nhất gồm ba số nguyên , và . Giá trị là khoảng cách theo phương ngang từ nguồn nước tới cửa ra của qanat. Giá trị là khoảng cách theo phương thẳng đứng từ nguồn nước tới mặt sườn núi. Giá trị là số giếng đứng phải dùng ngoài giếng mẹ.
Dữ liệu ra
Đầu tiên, in ra chi phí đào nhỏ nhất. Tiếp theo, in ra hoành độ của giếng đứng được đặt tối ưu, theo thứ tự tăng dần, mỗi số trên một dòng. Nếu , chỉ in hoành độ đầu tiên. Mỗi số được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá .
Bạn có thể giả sử lời giải tối ưu là duy nhất. Không có test nào mà lời giải tối ưu có một giếng cách cửa ra của kênh hoặc cách một giếng khác không quá đơn vị.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 4 1 | 31.500000 3.000000 |
Giếng duy nhất đặt tại , cao . |
| 195 65 2 | 12220.000000 48.000000 108.000000 |
Hai giếng đặt tại và . |
| 10000 1 1000 | 30141.885677 9.956721 19.913443 29.870164 39.826887 49.783610 59.740334 69.697060 79.653786 89.610515 99.567245 |
nên chỉ in hoành độ của giếng đầu tiên. |
Bình luận