시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 6 6 66.667%

문제

어떤 한 도시에는 수많은 갱들이 있다. 그리고 이 갱들은 여러 개의 직사각형 모양으로 된 영역을 차지하고 있다. 갱들은 서로의 영역 때문에 매번 싸움이 일어나곤 하는데, 영역 분쟁으로 너무나 많이 싸운 나머지 서로 피해가 이만저만이 아니다.

그래서, 한 갱의 두목인 정현식이 한 가지 아이디어를 냈다. 각 갱들이 자신의 영역을 하나씩 포기해서 분쟁 지역을 없애는 것이다.

이를 좀 더 자세하게 설명하자면 다음과 같다.

도시에 갱은 N(2 ≤ N ≤ 300)개가 존재하고, i번째 갱은 Mi(1 ≤ Mi ≤ 15)개의 영역을 가지고 있다. 도시는 계획적으로 지어졌기 때문에 도로가 반듯하게 지어져 있어 도시의 모든 영역을 손쉽게 xy 좌표로 나타낼 수 있다. 그리고 갱들의 각 영역은 xy 좌표에서 x축과 y축에 평행한 변을 가진 직사각형으로 나타내진다. 이때 영역의 네 꼭짓점을 x, y 값으로 나타냈을 때, x와 y는 0 이상 1,000,000 미만의 정수가 된다.

이때, 분쟁 지역은 서로 다른 갱이 가진 영역의 겹치는 부분을 말한다. 예를 들어서 갱 A가 갖고 있는 영역 중 한 영역이 (1,1) 부터 (10, 13)까지이고, 갱 B가 갖고 있는한 영역이 (9, 11) 부터 (20, 20)까지라면, 이 두 영역은 (9, 11)부터 (10, 13)까지 겹치기 때문에 이 겹치는 부분이 분쟁 지역이 된다. 서로의 영역이 선 또는 점만 겹치는 것은 분쟁 지역으로 취급하지 않는다. 예를 들어 (1,1)부터 (2,2)와 (1,2) 부터 (2,3)은 (1,2) 부터 (2,2) 까지의 테두리를 공유하지만, 이는 분쟁 지역이 아니다.

이에 대해, 정현식은 1부터 N에 대해 i번째 갱이 Mi개의 영역 중 하나를 포기하게 해서 분쟁 지역을 없애는 것을 목표로 하고 있다.

정현식은 이 방법을 사용하기 이전에 이 방법이 가능하긴 한 건지 알고 싶어 한다. 정현식을 도와 이 방법으로 현재 상황을 타파할 수 있는지 알려주자.

입력

첫 번째 줄에는 갱들의 숫자 N(2 ≤ N ≤ 300)이 들어온다.

두 번째 줄부터는 각 갱들의 영역에 대한 입력이 1번째 갱부터 N번째 갱까지 순서대로 연달아 들어온다.

i번째 갱에 대한 입력의 첫 번째 줄에는 갱이 가진 영역의 개수 Mi(2 ≤ Mi ≤ 15)이 들어온다.

그 다음 두 번째 줄 부터 Mi + 1 번째 줄 까지 각 영역의 왼쪽 아래 꼭짓점의 좌표와 오른쪽 위 꼭짓점의 좌표 x1, y1, x2, y2(0 ≤ x1 < x2 < 1,000,000, 0 ≤ y1 < y2 < 1,000,000) 가 띄어쓰기를 사이에 두고 입력으로 들어온다.

한 갱이 가진 영역들은 서로 겹치지 않는다.

출력

갱들이 영역을 하나씩 포기해서 분쟁 지역을 없앨 수 없다면 NO를 출력한다. 분쟁 지역을 없앨 수 있다면 YES를 출력한다.

예제 입력 1

2
2
1 1 4 5
100 100 101 101
3
1 1 3 3
3 3 6 7
90 95 105 110

예제 출력 1

YES

예제 입력 2

2
2
1 1 2 5
4 1 5 5
2
1 1 5 2
1 4 5 5

예제 출력 2

NO

힌트

첫 번째 예시 입력에서 1번 갱의 1번 영역 (1, 1) ∼ (4, 5)를 지우고, 2번 갱의 3번 영역 (90, 95) ∼ (105, 110)을 지우면, 1번 갱과 2번 갱의 영역이 서로 겹치지 않아 가능하다.

두 번째 예시 입력은 1번 갱의 영역과 2번 갱의 영역을 어떻게 지워도 항상 겹치는 영역이 하나 이상 존재해서 불가능하다.

출처

University > POSTECH > PPC 2018 G번