Submit solution
Points:
0.87 (partial)
Time limit:
0.38s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho ~M~ ~(M \le 100)~ hình tròn trên ~1~ bảng kích thước ~N \times N~ ô vuô~ng(N \le 1000)~, Mỗi hình tròn có ~1~ bán kính ~R_{i} -0.5~ ~(R_{i}~ nguyên, ~R_{i} \le 100)~ và tâm nằm trên trọng tâm của ~1~ ô vuông ở dòng ~x_{i}~, cột ~y_{i}~. Các hình tròn có thể đè lên nhau và có hình có một phần diện tích nằm ngoài bảng.
Yêu cầu: Tìm hình chữ nhật có diện tích lớn nhất nằm trên bảng mà không đè lên các hình tròn. Lưu ý: tất cả các dữ diệu input và output đều là số nguyên dương, kể cả kích thước và diện tích hình chữ nhật tìm được.
Input
Dòng đầu: số nguyên dương ~N~ và ~M~.
~M~ dòng sau: Mỗi dòng ghi ~3~ số, lần lượt là tọa độ hàng, cột của ô chứa tâm, bán kính hình tròn.
Output
- Diện tích của hình chữ nhật tìm được, và phần diện tích bị các hình tròn phủ (không tính phần diện tính lan ra khỏi bảng).
Sample Input
8 1
4 4 4
Sample Output
8 45
Comments