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