Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Diện tích hợp các hình chữ nhật (quét)

    Cho nnn hình chữ nhật trục song song, mỗi hình xác định bởi góc dưới-trái (x1,y1)(x_1, y_1)(x1​,y1​) và góc trên-phải (x2,y2)(x_2, y_2)(x2​,y2​). Tính diện tích phần hợp (phần được phủ bởi ít nhất một hình; phần chồng lấn chỉ tính một lần).

    Dùng nén tọa độ xxx và quét theo dải dọc.

    • Định dạng đầu vào:

      Dòng đầu: nnn. nnn dòng sau: mỗi dòng x1 y1 x2 y2x_1\ y_1\ x_2\ y_2x1​ y1​ x2​ y2​ với x1<x2x_1<x_2x1​<x2​, y1<y2y_1<y_2y1​<y2​.

    • Ràng buộc đầu vào:

      1≤n≤20001 \le n \le 20001≤n≤2000, ∣xi∣,∣yi∣≤109|x_i|,|y_i| \le 10^9∣xi​∣,∣yi​∣≤109.

    • Định dạng đầu ra:

      Một số nguyên: diện tích phần hợp.

    Ví dụ:

    Đầu vào:

    2
0 0 2 2
1 1 3 3

    Đầu ra:

    7

    Giải thích:

    Hai hình vuông cạnh 2 (diện tích 4 mỗi hình) chồng nhau vùng 1×1=1. Hợp = 4+4-1 = 7.

    Đang tải editor...