페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5790

Square Pasture 1초 512MB

문제

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 integerN. 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 ycoordinates are distinct from each-other. All x and y values lie in the range 0…10^9.

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 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
출력
420

출처

USACO 2020 December Gold

역링크 공식 문제집만