← 返回 microsoft 的题目列表Hash Map (Hard): Count point pairs satisfying a condition
类型：online_judge
Problem: Hash Map (Hard) - Count pairs of points meeting a condition
Given n points on a 2D plane points[i]=(xi, yi), count the number of unordered pairs such that their Manhattan distance equals D:
[ |x1-x2| + |y1-y2| = D ]
Input (stdin)
First line: n D
Next n lines: xi yi
Output
The number of unordered pairs satisfying the condition.
Constraints
1 <= n <= 2e5
0 <= D <= 2e5
-1e9 <= xi, yi <= 1e9
Example
Input:
5 2
0 0
2 0
1 1
0 2
3 0
Output:
3
Example
Input
5 2
0 0
2 0
1 1
0 2
3 0
Output
3