PreVOI 2025 - Contest 2 - Hạn hán

Xem dạng PDF

Gửi bài giải

Điểm: 110,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Test chính thức

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Ngôi làng X đang phải trải qua đợt hạn hán nghiêm trọng nhất trong lịch sử. Để đối phó với nạn hạn hán, các bô lão đã quyết định sẽ phân phối lại lượng nước tại các giếng nước trong ngôi làng tại các điểm dân cư, nhằm đảm bảo cung cấp đầy đủ lượng nước cho quá trình sinh hoạt của người dân.

Có ~n~ điểm dân cư trong ngôi làng, điểm dân cư thứ ~i~ có nằm ở tọa độ ~(x_i, y_i)~. Tại mỗi điểm dân cư đều có một giếng để có thể lưu trữ nước sạch, lượng nước hiện tại trong giếng ở điểm dân cư thứ ~i~ là ~a_i~ lít.

Các bô lão có thể dùng xe kéo để di chuyển nước giữa hai điểm dân cư bất kì. Tuy nhiên, do thời tiết nắng nóng kéo dài nên lượng nước sẽ bị hao hụt một lượng lít nước đúng bằng khoảng cách Euclide giữa hai điểm dân cư trong quá trình vận chuyển. Cụ thể, nếu vận chuyển ~x~ lít nước từ điểm dân cư ~i~ đến điểm dân cư ~j~ thì lượng nước mà thành phố ~j~ nhận được sẽ là ~\max(0, x-d_{i,j})~ lít với ~d_{i,j}~ là khoảng cách Euclide giữa hai điểm dân dân cư ~i~ và ~j~.

Các bô lão mong muốn tìm cách vận chuyển nước sao cho lượng nước tại giếng ít nước nhất là nhiều nhất có thể.

Yêu cầu: Hãy giúp các bô lão tìm ra lượng nước trên.

Input

  • Dòng đầu tiên chứa một số nguyên ~n~ ~(1 \le n \le 14)~ là số điểm dân cư.

  • Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm ba số nguyên ~x_i, y_i, a_i~ ~(0 \le x_i, y_i, a_i \le 10^9)~ là tọa độ và lượng nước trong giếng của điểm dân cư thứ ~i~. Dữ liệu vào đảm bảo không có hai điểm dân cư nào có cùng tọa độ.

Output

Gồm một số thực duy nhất là lượng nước lớn nhất có thể tại giếng ít nước nhất với cách vận chuyển nước tối ưu. Đáp án của bạn được xem là đúng nếu chênh lệch tương đối hoặc tuyệt đối so với đáp án của ban giám khảo không vượt quá ~10^{-6}~.

Scoring

Subtask Điểm Ràng buộc
1 ~20\%~ ~n \le 2~
2 ~20\%~ ~n \le 3~
3 ~30\%~ ~y_i = 0~
4 ~30\%~ Không có giới hạn gì thêm

Sample Input 1

3
1 1 10
3 1 5
1 6 8

Sample Output 1

6.500000000000

Sample Input 2

4
0 0 22
3 0 5
3 3 14
0 3 8

Sample Output 2

10.000000000000

Notes

Khoảng cách Euclide giữa hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ được tính bằng công thức ~\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}~.

Ở ví dụ đầu tiên, cách vận chuyển nước tối ưu là vận chuyển ~3.5~ lít nước từ điểm dân cư ~1~ đến điểm dân cư ~2~. Khi đó, điểm dân cư ~2~ sẽ nhận được ~\max(0, 3.5-d_{1,2}) = \max(0, 3.5-2) = 1.5~ lít nước. Lượng nước của các điểm dân cư trở thành ~[6.5, 6.5, 8]~, và lượng nước tại điểm dân cư có ít nước nhất là ~6.5~.

Ở ví dụ thứ hai, dưới đây là một cách vận chuyển nước tối ưu:

  • Vận chuyển ~8~ lít nước từ địa điểm ~1~ đến địa điểm ~2~. Địa điểm ~2~ sẽ nhận được ~5~ lít nước. Lượng nước của các Địa điểm trở thành ~[14, 10, 14, 8]~.

  • Vận chuyển ~4~ lít nước từ địa điểm ~3~ đến địa điểm ~4~. Địa điểm ~4~ sẽ nhận được ~1~ lít nước. Lượng nước của các địa điểm trở thành ~[14, 10, 10, 9]~.

  • Vận chuyển ~4~ lít nước từ địa điểm ~1~ đến địa điểm ~4~. Địa điểm ~4~ sẽ nhận được ~1~ lít nước. Lượng nước của các địa điểm trở thành ~[10, 10, 10, 10]~.

Lượng nước tại điểm dân cư có ít nước nhất là ~10~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


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