QJ105 - Diện tích cần sơn
Xem dưới dạng PDFMô tả bài toán: Một nhóm robot khảo cổ của hành tinh X đang làm việc tại một khu vực phế tích. Khu vực này có mặt đất rất cứng và phẳng như gương. Để tiện cho việc quản lý, người điều hành đã lập một hệ tọa độ Descartes tiêu chuẩn trên mặt đất. Mỗi robot đều có điểm mạnh riêng, sở hữu những kỹ năng đặc biệt và quan tâm đến các lĩnh vực khảo cổ khác nhau. Sau khi tiến hành các phép đo đạc, mỗi robot sẽ báo cáo một hoặc nhiều vùng hình chữ nhật ưu tiên khảo cổ. Các vùng hình chữ nhật này được biểu diễn dưới dạng tọa độ hai đỉnh đối diện $(x_{1}, y_{1}, x_{2}, y_{2})$. Để dễ dàng nhận biết và quản lý, trung tâm yêu cầu sơn màu vàng toàn bộ các vùng hình chữ nhật mà robot đã xác định. Tiểu Minh không trực tiếp làm thợ sơn, nhưng cậu ấy cần tính toán chính xác tổng diện tích các vùng cần sơn này. Nhiệm vụ này không quá phức tạp, chỉ cần tính diện tích tổng thể các vùng hình chữ nhật đã được robot xác định, đồng thời lưu ý rằng các hình chữ nhật này có thể bị chồng lên nhau.
Đầu vào của bài này là một số hình chữ nhật, yêu cầu xuất tổng diện tích mà chúng bao phủ.
Input: Dòng đầu tiên chứa một số nguyên $n$, biểu thị số lượng hình chữ nhật, $1 \le n < 10000$. $n$ dòng tiếp theo, mỗi dòng có $4$ số nguyên $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$, cách nhau bởi khoảng trắng, biểu thị tọa độ hai đỉnh đối diện của hình chữ nhật, $0 \le x_{1}, y_{1}, x_{2}, y_{2} \le 10000$.
Output: Xuất một số nguyên, biểu thị tổng diện tích mà các hình chữ nhật bao phủ.
Input mẫu:
3
1 5 10 10
3 1 20 20
2 7 15 17
Output mẫu:
340
Nhận xét