← 返回题目列表

AtCoder · abc366_e

H. 曼哈顿多焦点椭圆

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

你被给予 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
  • (x_i, y_i) \neq (x_j, y_j) 为 i \neq 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

下图可视化了 Sample 的输入和答案 1。蓝点代表输入。蓝点和红点共八个,满足语句中的条件。


示例输入 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