C11CIR - Những hình tròn
Giới hạn- Thời gian: 0.2s
- 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.
Cho M (M<= 100) hình tròn trên 1 bảng kích thước N*N ô vuông(N <= 1000), Mỗi hình tròn có 1 bán kính R[i]-0.5 (R[i] nguyên, R[i] <= 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.
Ví dụ: Hình tròn có tâm (4;4), bán kính là 4 và phần bị phủ là phần màu đỏ.
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).
Ví dụ
Input: 8 1
4 4 4
Output: 8 45
- Người up: yenthanh132
- Nguồn bài: Khải Hạnh