/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 475 点
問題文
2 次元平面上の N 個の点 (x_1,y_1),(x_2,y_2),\dots,(x_N,y_N) と、非負整数 D が与えられます。
整数の組 (x,y) であって、 \displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D を満たすものの個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^6
- -10^6 \leq x_i, y_i \leq 10^6
- i\neq j ならば (x_i,y_i) \neq (x_j,y_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D x_1 y_1 x_2 y_2 \vdots x_N y_N
出力
答えを出力せよ。
入力例 1
2 3 0 0 1 0
出力例 1
8
下図は、サンプル 1 の入力と答えを可視化したものです。青い点が入力を表します。青い点と赤い点の合計 8 点が、問題文中の条件を満たす点です。
入力例 2
2 0 0 0 2 0
出力例 2
0
入力例 3
6 100 9 -6 10 -1 2 10 -1 7 -7 5 -1 -4
出力例 3
419
Score : 475 points
Problem Statement
You are given N points (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) on a two-dimensional plane, and a non-negative integer D.
Find the number of integer pairs (x, y) such that \displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^6
- -10^6 \leq x_i, y_i \leq 10^6
- (x_i, y_i) \neq (x_j, y_j) for i \neq j.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D x_1 y_1 x_2 y_2 \vdots x_N y_N
Output
Print the answer.
Sample Input 1
2 3 0 0 1 0
Sample Output 1
8
The following figure visualizes the input and the answer for Sample 1. The blue points represent the input. The blue and red points, eight in total, satisfy the condition in the statement.
Sample Input 2
2 0 0 0 2 0
Sample Output 2
0
Sample Input 3
6 100 9 -6 10 -1 2 10 -1 7 -7 5 -1 -4
Sample Output 3
419