时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
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≤N≤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.
输入描述:
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
说明
In this example, there are 24 subsets in total. FJ cannot create a fence enclosing only cows 1 and 3, or only cows 2 and 4, so the answer is 24−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
说明
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