#PU1067. USACO 2020 December Contest, Gold — Problem 3. Square Pasture

    ID: 1185 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec20来源:usaco.orgscoring:equal_test_cases前缀和二分

USACO 2020 December Contest, Gold — Problem 3. Square Pasture

USACO 2020 December Contest, Gold — Problem 3. Square Pasture

题目描述

Farmer John's largest pasture can be regarded as a large 2D grid of square "cells" (picture a huge chess board). Currently, there are NN cows occupying some of these cells (1≤N≤2001 \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 xx and yy 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.

输入格式

The first line contains a single integer NN. Each of the next NN lines Each of the next NN lines contains two space-separated integers, indicating the (x,y)(x,y) coordinates of a cow's cell. All xx coordinates are distinct from each-other, and all yy coordinates are distinct from each-other. All xx and yy values lie in the range 0…1090 \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.

数据范围

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

样例

样例 1

4
0 2
2 3
3 1
1 0
14
In 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$.

样例 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

提示

square fenced area might possibly extend into cells with negative coordinates.