Forest Fires
Contest: Codeforces Round 528 (Div. 1, based on Technocup 2019 Elimination Round 4)
Difficulty rating: 3500
Tags: math

Berland forest was planted several decades ago in a formation of an infinite grid with a single tree in every cell. Now the trees are grown up and they form a pretty dense structure.

So dense, actually, that the fire became a real danger for the forest. This season had been abnormally hot in Berland and some trees got caught on fire!

The second fire started is considered the second $$$0$$$. Every second fire lit up all intact neightbouring trees to every currently burning tree. The tree is neighbouring if it occupies adjacent by side or by corner cell. Luckily, after $$$t$$$ seconds Berland fire department finally reached the location of fire and instantaneously extinguished it all.

Now they want to calculate the destructive power of the fire. Let $$$val_{x, y}$$$ be the second the tree in cell $$$(x, y)$$$ got caught on fire. The destructive power is the sum of $$$val_{x, y}$$$ over all $$$(x, y)$$$ of burnt trees.

Clearly, all the workers of fire department are firefighters, not programmers, thus they asked you to help them calculate the destructive power of the fire.

The result can be rather big, so print it modulo $$$998244353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 50$$$, $$$0 \le t \le 10^8$$$) — the number of trees that initially got caught on fire and the time fire department extinguished the fire, respectively.

Each of the next $$$n$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$-10^8 \le x, y \le 10^8$$$) — the positions of trees that initially got caught on fire.

Obviously, the position of cell $$$(0, 0)$$$ on the grid and the directions of axes is irrelevant as the grid is infinite and the answer doesn't depend on them.

It is guaranteed that all the given tree positions are pairwise distinct.

The grid is infinite so the fire doesn't stop once it reaches $$$-10^8$$$ or $$$10^8$$$. It continues beyond these borders.

Output format:
Print a single integer — the sum of $$$val_{x, y}$$$ over all $$$(x, y)$$$ of burnt trees modulo $$$998244353$$$.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
Here are the first three examples. The grey cells have $$$val = 0$$$, the orange cells have $$$val = 1$$$ and the red cells have $$$val = 2$$$.

Example input:
1 2
10 11

Example output:
40

Example input:
4 1
2 2
1 3
0 2
2 4

Example output:
18

Editorial:
Let $$$f(t)$$$ be the total number of trees burnt during first $$$t$$$ seconds. The answer can be represented as $$$t f(t) - \sum \limits_{i = 0}^{t - 1} f(i)$$$. Computing one value of $$$f(t)$$$ can be done in $$$O(n^2)$$$ or $$$O(n \log n)$$$ with scanline or something like that.
Let's analyze how the value of this function is changed as time goes. In the beginning, only $$$n$$$ initial trees are burnt, then the zones around their position, expand, and so on, until two zones start intersecting. Then again, until another pair of zones starts intersecting. And so on. Let $$$x_1, x_2, \dots, x_k$$$ be the sorted sequence of moments when two zones start intersecting (this sequence has no more than $$$O(n^2)$$$ elements and can easily be computed in $$$O(n^2 \log n)$$$). Let's analyze the behavior of the function $$$f(t)$$$ on segments $$$[0, x_1 - 1], [x_1, x_2 - 1]$$$ and so on.
Why are we interested in such segments? Because for each such segment, $$$f(t)$$$ can be represented as a polynomial. This can be proven with the help of inclusion-exclusion: for each subset of zones, the intersection of zones is either empty or a rectangle. And if we expand the rectangle, then during second $$$0$$$ its area is $$$ab$$$, during second $$$1$$$ — $$$(a + 2)(b + 2)$$$, during second $$$t$$$ — $$$(a + 2t)(b + 2t)$$$, it's a $$$2$$$-nd degree polynomial. So if we would try to compute the area of affected land through inclusion-exclusion formula, we would get a sum of no more than $$$2^n$$$ polynomials, each having degree no more than $$$2$$$, so the result is also a $$$2$$$-nd degree polynomial. We can actually compute the coefficients of this polynomial by interpolation or just some pen and paper work. And $$$f(x_i) + f(x_{i} + 1) + f(x_{i} + 2) + \dots + f(x_{i + 1} - 1)$$$ is a polynomial of $$$3$$$-rd degree, which can be computed using some more pen and paper work.
So, to conclude, the solution consists of two steps:
1. find all the moments when two zones affected by different trees start intersecting;
2. consider the function on the segments when it behaves as a polynomial.