Những hình tròn

View as PDF

Submit solution

Points: 0.87 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Khải Hạnh
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

Please read the guidelines before commenting.


There are no comments at the moment.