Gửi bài giải
Điểm:
0,25 (OI)
Giới hạn thời gian:
0.9s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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?
Input
- Dòng ~1~: một số nguyên ~N~ là số hộ dân ~(1 \leq N \leq 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 \leq x_{i}~, ~y_{i} \leq 50~, ~30 \leq s_{i} \leq 500)~.
Output
- 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.
Sample Input
5
0 0 1
1 1 2
2 2 4
0 1 5
1 0 3
Sample Output
51
Bình luận