교차하는 직사각형
시간 제한2초메모리 제한512 MB
모든 x좌표와 y좌표가 서로 다른 n개의 축에 평행한 직사각형이 주어질 때, 두 직사각형의 경계가 만나는 쌍이 있는지 판정한다. 한 직사각형이 다른 직사각형을 완전히 포함하는 경우는 제외한다.
문제
2차원 평면 위에 축에 평행한 직사각형 n개가 주어진다. 두 직사각형의 경계가 공통인 점을 가지면 두 직사각형이 교차한다고 한다. 특히 한 직사각형이 다른 직사각형을 완전히 포함하는 경우는 교차하지 않는 것으로 본다. 교차하는 직사각형 쌍이 존재하는지 판별하라.
이 예에서 직사각형 A와 B만 교차한다.
입력
각 테스트 케이스의 첫 줄에는 직사각형의 개수 n (1 ≤ n ≤ 105)이 주어진다.
다음 n개 줄에는 각각 네 개의 정수가 공백으로 구분되어 주어진다.
x1 y1 x2 y2
(−109 ≤ x1, y1, x2, y2 ≤ 109, x1 < x2, y1 < y2)는 하나의 직사각형을 나타내며, (x1, y1)은 왼쪽 아래 꼭짓점, (x2, y2)는 오른쪽 위 꼭짓점이다. 모든 x 값은 서로 다르고, 모든 y 값도 서로 다르다.
출력
교차하는 직사각형 쌍이 존재하면 1, 존재하지 않으면 0을 출력한다.