Square Pasture
플래티넘 I의견: 0
Farmer John's largest pasture can be regarded as a large 2D grid of square
"cells" (picture a huge chess board). Currently, there are \(N\) cows occupying
some of these cells (\(1 \leq N \leq 200\)).
Farmer John wants to build a fence that will enclose a square region of cells;
the square must be oriented so its sides are parallel with the \(x\) and \(y\)
axes, and it could be as small as a single cell. Please help him count the
number of distinct subsets of cows that he can enclose in such a region. Note
that the empty subset should be counted as one of these.
Problem credits: Benjamin Qi
SCORING
- In test cases 1-5, all coordinates of cells containing cows are less than \(20\).
- In test cases 6-10, \(N\le 20\).
- In test cases 11-20, there are no additional constraints.
Problem credits: Benjamin Qi
The first line contains a single integer \(N\). Each of the next \(N\) lines Each
of the next \(N\) lines contains two space-separated integers, indicating the
\((x,y)\) coordinates of a cow's cell. All \(x\) coordinates are distinct from
each-other, and all \(y\) coordinates are distinct from each-other. All \(x\) and
\(y\) values lie in the range \(0 \ldots 10^9\).
The number of subsets of cows that FJ can fence off. It can be shown that this
quantity fits within a signed 32-bit integer.
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
평가 및 의견
Square Pasture
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Square Pasture