레이팅 미적용농부 존의 가장 큰 목초지는 정사각형 "칸"들로 이루어진 큰 2차원 격자(거대한 체스판을 떠올려 보자)로 볼 수 있다. 현재 \(N\)마리의 소가 이 칸들 중 일부를 차지하고 있다(\(1 \leq N \leq 200\)).
농부 존은 정사각형 모양의 칸 영역을 둘러싸는 울타리를 세우려고 한다. 정사각형의 변은 \(x\)축과 \(y\)축에 평행해야 하며, 칸 하나만큼 작을 수도 있다. 이러한 영역으로 둘러쌀 수 있는 서로 다른 소들의 부분집합의 개수를 세어 농부 존을 도와주자. 공집합도 그중 하나로 세어야 함에 유의한다.
문제 제공: Benjamin Qi
배점
- 테스트 케이스 1-5에서는 소가 있는 칸의 모든 좌표가 \(20\)보다 작다.
- 테스트 케이스 6-10에서는 \(N\le 20\)이다.
- 테스트 케이스 11-20에서는 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 정수 \(N\)이 주어진다. 다음 \(N\)개의 줄 각각에는 공백으로 구분된 두 정수가 주어지며, 이는 소가 있는 칸의 \((x,y)\) 좌표를 나타낸다. 모든 \(x\) 좌표는 서로 다르고, 모든 \(y\) 좌표도 서로 다르다. 모든 \(x\)와 \(y\) 값은 \(0 \ldots 10^9\) 범위에 있다.
농부 존이 울타리로 둘러쌀 수 있는 소들의 부분집합의 개수를 출력한다. 이 값은 부호 있는 32비트 정수 범위에 들어감이 보장된다.
4
0 2
2 3
3 1
1 014In this example, there are \(2^4\) subsets in total. FJ cannot create a fence enclosing only cows 1
and 3, or only cows 2 and 4, so the answer is \(2^4-2=16-2=14\).
16
17 4
16 13
0 15
1 19
7 11
3 17
6 16
18 9
15 6
11 7
10 8
2 1
12 0
5 18
14 5
13 2420riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > December > Gold