NC222474. [USACODec2020G]SquarePasture

描述

输入描述

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…109.
Note that although the coordinates of cells with cows are nonnegative, the square fenced area might possibly extend into cells with negative coordinates.

输出描述

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.

示例1

输入:

4
0 2
2 3
3 1
1 0

输出:

14

说明:

In this example, there are 2⁴ 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⁴−2=16−2=14.

示例2

输入:

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 2

输出:

420

说明:

In test cases 1-5, all coordinates of cells containing cows are less than 20.
In test cases 6-10, N≤20.
In test cases 11-20, there are no additional constraints.
Problem credits: Benjamin Qi

原站题解