Xóa Điểm

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Cho $N$ điểm trên mặt phẳng tọa độ vô hạn ( $N$ chẵn, $2 \leq N \leq 10^{5}$ ), điểm thứ $i$ có tọa độ $(x_{i}, y_{i})$ .

Có hai phép biến đổi:

Xóa cặp kề: Chọn hai điểm có khoảng cách Manhattan bằng $1$ và xóa cả hai.
Hoán đổi tọa độ $y$ : Chọn hai điểm $(a, b)$ và $(c, d)$ bất kỳ, biến chúng thành $(a, d)$ và $(c, b)$ .

Xác định xem có thể xóa tất cả các điểm hay không.

Lưu ý: Các điểm tại cùng tọa độ là phân biệt và không thể xóa trực tiếp với nhau (khoảng cách Manhattan bằng $0$ , không phải $1$ ).

Dòng 1: Số nguyên $T$ — số bộ test ( $1 \leq T \leq 5000$ )
Với mỗi bộ test:
- Dòng 1: Số nguyên $N$ (chẵn)
- $N$ dòng tiếp theo: Hai số nguyên $x_{i}, y_{i}$ ( $1 \leq x_{i}, y_{i} \leq 10^{6}$ )

Tổng $N$ trên tất cả bộ test không vượt quá $5 \times 10^{5}$ .

Với mỗi bộ test, in YES hoặc NO.

Input	Output	Giải thích
4 2 1 1 1 1 4 6 10 7 11 8 1 8 1 6 1 2 1 3 1 4 1 5 10 10 11 10 6 1 1 1 1 1 1 1 1 10 10 11 11	NO YES YES NO	Test 1: Hai điểm trùng nhau, khoảng cách $0$ , không xóa được. Test 2: Hoán đổi $y$ rồi ghép cặp kề.

Bình luận

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