INTERSECT - INTERSECT
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.5 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: a516zxa

Hôm nay anh CaiWinDao quyết định thử thách ba thanh niên zxa, ami và thánh ngốc 1 bài toán hóc búa và phần thưởng là 500000 USD cho mỗi bạn. Nhưng không may vì quá bận rộn nên cả 3 bạn không có thời gian làm nhưng đồng thời cũng không muốn đánh mất quà. Vì vậy các thanh niên đã nhờ các bạn thí sinh Contest10 giúp đỡ. Các bạn hãy giúp họ nhé!

 

Bài toán rất đơn giản: 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).

 

Dữ liệu vào:

- Dòng đầu tiên chứ số nguyên n (1 <= n <= 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 <= x1, y1, x2, y2 <= 10^9, x1 < x2, y1 < y2).


Kết quả:

- 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).

 

Ví dụ

Input 1:

2
0 0 2 2
2 2 3 4

Ouput 1:

0

Input 2:

2
1 1 3 3
2 2 10 4

Output 2:

1

Back to Top