GPMB - Giải phóng mặt bằng
Giới hạn- Thời gian: 0.6s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Chính quyền thành phố KN đang tiến hành mở thêm một tuyến đường mới trong thành phố. Chính quyền có bản đồ tọa độ của N hộ dân trong khu vực tuyến đường có thể đi qua. Tuyến đường là một đường thẳng đi qua tọa độ các hộ dân. Các hộ dân được đánh số từ 1 đến N; hộ dân thứ i có diện tích sử dụng là s i (m 2 ). Nếu tuyến đường đi ngang qua hộ dân thứ i, chính quyền cần phải đền bù cho hộ dân này s i 2 +5 (đồng) tiền giải phóng mặt bằng. Hỏi chính quyền cần phải đền bù nhiều nhất bao nhiêu tiền khi xây dựng tuyến đường?
Dữ liệu
- Dòng 1: một số nguyên N là số hộ dân (1 ≤ N ≤ 1500).
- Dòng thứ i trong N dòng tiếp theo chứa 3 số nguyên x i , y i , s i cho biết tọa độ và diện tích của hộ dân thứ i (-50 ≤ x i , y i ≤ 50, 30 ≤ s i ≤ 500).
Kết quả
In ra một số duy nhất là số tiền nhiều nhất chính quyền phải đền bù khi xây dựng tuyến đường.
Ví dụ
Dữ liệu 5 0 0 1 1 1 2 2 2 4 0 1 5 1 0 3 Kết quả 51
- Người up: voj
- Nguồn bài: HAOI 2008 - Day 1 - Author: Ngô Minh Ðức