레이팅 미적용이전 작품이 평단의 찬사를 받은 뒤, 베시는 그림 세트를 디자인하는 일을 제안받았다. 베시는 평면 위에 축에 평행한 직사각형 \(1\le N\le 10^5\)개를, 어떤 두 변도 같은 직선 위에 놓이지 않도록 골라서 그림을 디자인한다. 이 직사각형들의 경계가 그림의 색칠된 영역들의 경계를 정의한다.
여전히 아방가르드 예술가인 베시는 그림이 홀스타인 소를 닮아야 한다고 결정한다. 구체적으로, 직사각형들이 만드는 각 영역은 검은색 또는 흰색으로 칠해지고, 인접한 두 영역은 같은 색이 아니며, 모든 직사각형 바깥의 영역은 흰색으로 칠해진다.
직사각형을 고른 뒤, 베시는 매개변수 \(T\)에 따라 다음 둘 중 하나를 출력해 주기를 원한다.
- \(T=1\)이면, 전체 영역의 수를 출력한다.
- \(T=2\)이면, 흰색 영역의 수와 검은색 영역의 수를 차례로 출력한다.
*참고: 이 문제의 시간 제한은 4초로, 기본값의 두 배이다.*
Problem credits: Andi Qu
채점 방식
- 테스트 케이스 3-4는 \(N\le 10^3\)을 만족한다.
- 테스트 케이스 5-7에서는 어떤 두 직사각형의 경계도 교차하지 않는다.
- 테스트 케이스 8-10에서는 \(T=1\)이고 모든 직사각형의 경계가 연결되어 있다.
- 테스트 케이스 11-13에서는 \(T=2\)이고 모든 직사각형의 경계가 연결되어 있다.
- 테스트 케이스 14-18에서는 \(T=1\)이다.
- 테스트 케이스 19-23에서는 \(T=2\)이다.
Problem credits: Andi Qu
첫째 줄에 \(N\)과 \(T\)가 주어진다.
다음 \(N\)개의 줄에는 각 직사각형에 대한 설명이 \((x_1,y_1), (x_2,y_2)\)의 형태로 주어진다. 여기서 \(1\le x_1
모든 \(x_i\)는 \(1\ldots 2N\)의 순열을 이루며, 모든 \(y_i\)에 대해서도 마찬가지임이 보장된다.
\(T=1\)이면 정수 하나를, 그렇지 않으면 공백으로 구분된 정수 두 개를 출력한다.
2 1
1 1 3 3
2 2 4 44There are two white regions and two black regions, for a total of four regions.
The boundaries of all rectangles are connected, so this input would satisfy the
conditions of subtask 3.
5 2
1 5 3 6
5 4 7 9
4 1 8 3
9 8 10 10
2 2 6 74 5The boundary of the rectangle in the upper-right is not connected to the rest of
the boundaries, so this input would not satisfy the conditions of subtask 4.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > February > Platinum