INTERSECT

Xem PDF

Điểm: 1800 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho n hình chữ nhật kích thước khác nhau được đại diện bằng góc trái dưới và góc phải trên. Các bạn hãy kiểm tra có ít nhất một cặp hình chữ nhật cắt nhau không. Một cặp hình chữ nhật cắt nhau khi tồn tại ít nhất một điểm của hình chữ nhật này nằm hoàn toàn trong hình chữ nhật còn lại (không tính các điểm nằm trên cạnh) và chúng không lồng nhau.

Input

  • Dòng đầu tiên chứ số nguyên \(n\) (\(1 \leq n \leq 10^{5}\)).
  • N dòng tiếp theo, mỗi dòng chứ 4 số nguyên \(x1\), \(y1\), \(x2\), \(y2\) lần lượt tọa độ của góc trái dưới và góc phải trên của hình chữ nhật (\(-10^{9} \leq x1, y1, x2, y2 \leq 10^{9}\), \(x1 < x2, y1 < y2\)).

Output

  • Gồm một dòng duy nhất: chứa số 1 (có ít nhất 1 cặp hình chữ nhật giao nhau) hoặc 0 (không chứa bất kì một cặp hình chữ nhật nào giao nhau).

Example

Test 1

Input
2    
0 0 2 2    
2 2 3 4
Output
0

Test 1

Input
2    
1 1 3 3    
2 2 10 4
Output
1

Bình luận

Không có bình luận nào.