canuc80k0108·9/50

Ma Trận Sau Những Lần Quay

Nộp bài trên LQDOJ

Bài 01 · Ad Hoc

Cho một ma trận có bốn số nguyên đôi một khác nhau. Ma trận được gọi là đẹp khi:

  • trong mỗi hàng, số bên trái nhỏ hơn số bên phải;
  • trong mỗi cột, số phía trên nhỏ hơn số phía dưới.

Bạn được phép quay toàn bộ ma trận 90° theo chiều kim đồng hồ bao nhiêu lần tùy ý. Hãy xác định có thể thu được một ma trận đẹp hay không.

Input

  • Dòng đầu chứa số nguyên .
  • Mỗi test gồm hai dòng, mỗi dòng chứa hai số nguyên của một hàng ma trận.

Output

  • Với mỗi test, in YES nếu có thể quay hoặc lần để ma trận đẹp; ngược lại in NO.

Constraints

  • .
  • Bốn phần tử của mỗi ma trận đôi một khác nhau.
  • Mỗi phần tử nằm trong .

Scoring

  • Subtask ( số điểm): .
  • Subtask ( số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

4
1 3
2 4
3 1
4 2
1 4
2 3
4 3
2 1

Output

YES
YES
NO
YES

Giải thích: Test đã đẹp; test và trở thành đẹp sau khi quay. Ở test , số nhỏ nhất và số lớn nhất nằm kề nhau nên không hướng quay nào thỏa đồng thời cả hàng và cột.

Lời giải tóm tắt
  • Ý tưởng: Sau bốn lần quay, ma trận trở về ban đầu, nên chỉ cần thử đúng bốn trạng thái tương ứng 0,1,2,3 lần quay. Với [a b; c d], ma trận sau một lần quay là [c a; d b]. Ở mỗi trạng thái, kiểm tra a<b, c<d, a<c, b<d. Nếu một trạng thái đúng thì in YES; nếu cả bốn sai thì in NO. Độ phức tạp O(1) mỗi test.