1331: 신천을 볼 수 있는 집 구하기
[만든사람 : DaegunOJ-admin 2023/01/10]
문제 설명
순찬이는 신천을 바라볼 수 있는 집에 살고 싶다. 그러나 신천을 온전히 볼 수 있는 집은 순찬이에게는 너무 가격이 높았다. 순찬이는 신천이 아주 조금이라도 보인다면 신천을 바라볼 수 있다는 것으로 만족하려고 한다.
순찬이는 귀찮음 대마왕이었기 때문에, 집을 직접 보러가기 전에 집에서 신천이 볼 수 있는지 알고 싶었다. 그래서 좌표평면을 이용하여 상황을 단순화시켜서 집에서 신천을 볼 수 있는지 알아보기로 하였다.
모든 집은 각 변이 x축과 y축에 평행한 직사각형 모양이며, 건물 너머를 볼 수 없다. 즉, 시야를 가린다.
순찬이는 귀찮음 대마왕이었기 때문에, 집을 직접 보러가기 전에 집에서 신천이 볼 수 있는지 알고 싶었다. 그래서 좌표평면을 이용하여 상황을 단순화시켜서 집에서 신천을 볼 수 있는지 알아보기로 하였다.
- 신천은 y=0인 좌우로 무한히 뻗은 직선이라고 가정한다.
- 집은 2차원 좌표평면 상의 점 하나로 취급하기로 하였다.
- 순찬의 시야는 y축 아래 방향으로 좌우 45°이다.
모든 집은 각 변이 x축과 y축에 평행한 직사각형 모양이며, 건물 너머를 볼 수 없다. 즉, 시야를 가린다.
신천을 볼 수 있는 집
신천을 볼 수 없는 집
주변 지도 데이터가 주어질 때, 순찬이의 궁금증을 해결해주자.
입력 설명
첫째 줄에 건물의 개수 n ( 1 ≤ n ≤ 200,000 )이 주어진다.
둘째 줄에 집의 위치 x0, y0가 주어진다. ( -109 ≤ x0 ≤ 109, 0 < y0 ≤ 109 )
셋째 줄부터 n줄에 걸쳐 각 건물의 왼쪽 위의 좌표 x1, y1과 오른쪽 아래의 좌표 x2, y2가 순서대로 공백으로 분리되어 주어진다. ( -109 ≤ x1 < x2 ≤ 109, 0 < y2 < y1 < y0 )
모든 좌표는 정수이며, 건물들끼리 겹치거나 경계가 맞닿는 경우는 없다.
출력 설명
집에서 신천을 바라볼 수 있으면 Yes, 그렇지 않으면 No를 출력한다.
입력 예시 Copy
4
0 6
-4 5 -1 4
-2 3 1 2
-7 2 -4 1
2 2 5 1
출력 예시 Copy
Yes