E - Manhattan Multifocal Ellipse

Contest Duration: 2024-08-10(Sat) 12:00 - 2024-08-10(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Manhattan Multifocal Ellipse Editorial

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$

出力

答えを出力せよ。

入力例 1Copy

Copy

2 3
0 0
1 0

出力例 1Copy

Copy

下図は、サンプル $1$ の入力と答えを可視化したものです。青い点が入力を表します。青い点と赤い点の合計 $8$ 点が、問題文中の条件を満たす点です。

入力例 2Copy

Copy

2 0
0 0
2 0

出力例 2Copy

Copy

入力例 3Copy

Copy

出力例 3Copy

Copy

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 1Copy

Copy

2 3
0 0
1 0

Sample Output 1Copy

Copy

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 2Copy

Copy

2 0
0 0
2 0

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy