Tô Màu Hình Chữ Nhật

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie đang thiết kế các bức tranh bằng cách vẽ $N$ hình chữ nhật có các cạnh song song với trục tọa độ. Các đường biên của các hình chữ nhật này chia mặt phẳng thành các vùng màu xen kẽ đen và trắng, tạo thành hoa văn giống hoa văn trên bò Holstein. Vùng bên ngoài (vô hạn) luôn có màu trắng.

Cụ thể hơn, định nghĩa vùng là một tập hợp các điểm liên thông cực đại sao cho mọi đường đi giữa hai điểm bất kỳ trong vùng đó không cắt qua bất kỳ cạnh nào của hình chữ nhật. Màu của một vùng được xác định bởi tính chẵn lẻ của số lần đường biên hình chữ nhật được cắt khi đi từ vùng đó ra vùng ngoài cùng: nếu số lần cắt là chẵn thì vùng có màu trắng, nếu lẻ thì màu đen.

Với tham số $T$ , hãy xuất tổng số vùng (nếu $T = 1$ ), hoặc số vùng trắng và số vùng đen riêng biệt (nếu $T = 2$ ).

Dữ liệu vào

Dòng đầu tiên: Hai số nguyên $N$ và $T$ .
$N$ dòng tiếp theo: Mỗi dòng chứa bốn số nguyên $x_{1}$ , $y_{1}$ , $x_{2}$ , $y_{2}$ mô tả một hình chữ nhật với góc dưới-trái $(x_{1}, y_{1})$ và góc trên-phải $(x_{2}, y_{2})$ .

Dữ liệu ra

Nếu $T = 1$ : In ra một số nguyên duy nhất là tổng số vùng.
Nếu $T = 2$ : In ra hai số nguyên phân cách bởi dấu cách: số vùng trắng và số vùng đen.

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq x_{1} < x_{2} \leq 2 N$ và $1 \leq y_{1} < y_{2} \leq 2 N$
Tất cả các tọa độ $x$ tạo thành một hoán vị của $1, 2, \dots, 2 N$ (không có hai cạnh dọc nào trùng nhau).
Tất cả các tọa độ $y$ tạo thành một hoán vị của $1, 2, \dots, 2 N$ (không có hai cạnh ngang nào trùng nhau).

Ví dụ

Input	Output	Giải thích
2 1 1 1 3 3 2 2 4 4	4	Hai hình chữ nhật chồng lên nhau tạo ra 4 vùng: vùng ngoài (trắng), phần chỉ thuộc HCN 1 (đen), phần giao nhau của hai HCN (trắng), phần chỉ thuộc HCN 2 (đen).
5 2 1 5 3 6 5 4 7 9 4 1 8 3 9 8 10 10 2 2 6 7	4 5	Có 4 vùng trắng và 5 vùng đen.

Ghi chú

Trong ví dụ 1: Hai hình chữ nhật giao nhau tạo ra đúng 4 vùng phân biệt.

Trong ví dụ 2: Các hình chữ nhật tạo ra tổng cộng 9 vùng, trong đó 4 vùng trắng và 5 vùng đen (kể cả vùng ngoài vô hạn màu trắng).

Bình luận

Không có bình luận tại thời điểm này.