Phân mảnh không gian


Submit solution

Points: 4
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

Cho \(N\) hình chữ nhật được đặt trong không gian \(Oxy\). Những hình chữ nhật này có thể chồng lên nhau hoặc tách rời nhau và chia không gian thành các vùng riêng biệt.

Nhiệm vụ của bạn là đếm số vùng riêng biệt đã được tạo ra.

Minh họa 2 test ví dụ:

Test case 1 Test case 2

Đầu vào

Dòng đầu tiên là số lượng bộ test \(T\). \((1 \le T \le 200)\)

Mỗi bộ test gồm số nguyên dương \(N\) là số hình chữ nhật trong không gian. \((1 \le N \le 50)\)

\(N\) dòng tiếp theo, mỗi dòng gồm \(4\) số nguyên \(xA, yA, xB, yB\) là tọa độ của góc trái trên và góc phải dưới của hình chữ nhật thứ \(i\). \((0 \le xA, yA, xB, yB \le 10^6)\)

Đầu ra

Với mỗi test, in ra số lượng các vùng riêng biệt được tạo ra bởi \(N\) hình chữ nhật đã cho.

Giới hạn

\(20\%\) số test có \(T = 1\), \(N \le 10\), tọa độ \(\le 100\).

\(30\%\) số test có \(T \le 50\), \(N \le 10\), tọa độ \(\le 10^6\).

\(50\%\) số test còn lại không có ràng buộc gì thêm.

Ví dụ

Đầu vào

2 
3
4 28 27 11
15 20 42 5
11 24 33 14
5
4 28 27 11
12 11 34 2
7 26 14 16
14 16 19 12
17 28 27 21

Đầu ra

8
6

Comments

There are no comments at the moment.