菜王的 blog

最构式的一集。

下面定义原题中输入的八个变量依次为 $A, B, C, D, E, F, G, H$。

不考虑多边形面积非零这条限制，我们相当于是在统计自然数八元组 $(a, b, c, d, e, f, g, h)$，满足：

• $(a, b, c, d, e, f, g, h)$ 被 $(A, B, C, D, E, F, G, H)$ 偏序（不一定严格）；
• $a \cdot (0, 1) + b \cdot (-1, 1) + c \cdot (-1, 0) + d \cdot (-1, -1) + e \cdot (0, -1) + f \cdot (1, -1) + g \cdot (1, 0) + h \cdot (1, 1) = (0, 0)$。

最后将答案减去 $\min(a, e) + \min(b, f) + \min(c, g) + \min(d, h) + 1$ 即可。

跳过一些推导，我们可以得到：

$a - e = f - b + d - h\\ c - g = f - b + h - d\\$

将其改写成下列形式：

$P = e - a, X = b - f, Q = g - c, Y = d - h\\ X - Y = P\\ X + Y = Q\\$

定义 $calc(A, B, x)$ 为满足 $0 \le a \le A, 0 \le b \le B, a - b = x$ 的自然数对 $(a, b)$ 个数，那么有 $calc(A, B, x) = \max(\min(A, B - x) + \min(0, x) + 1, 0)$。

令 $f_a(x) = calc(E, A, x), f_b(x) = calc(B, F, x), f_c(x) = calc(G, C, x), f_d(x) = calc(D, H, x)$，那么对于一对 $X, Y$，答案为 $f_a(X - Y)f_b(X)f_c(X + Y)f_d(Y)$，可以 $O(1)$ 计算，那么我们枚举 $X, Y$ 即可做到 $O(N^2)$。

考虑少枚举一维。$calc(*)$ 显然是一个只有 $O(1)$ 段的分段一次函数，对于一个确定的 $Y$，定义 $f_Y(X) = f_a(X - Y)f_b(X)f_c(X + Y)$，那么 $f_Y$ 是一个只有 $O(1)$ 段的分段三次函数，它的断点由 $f_a, f_b, f_c$ 的断点平移后合并得到。考虑对每一段做个插值就能快速算出一段的 $f_Y$ 之和。这样对于一个确定的 $Y$，可以 $O(1)$ 计算 $\sum_X f_Y(X)$，那么我们枚举 $Y$ 即可做到 $O(N)$。

继续优化。定义 $f'(Y) = f_d(Y) \sum_X f_Y(X)$，我们尝试用类似的方法优化之。可以感觉到，$f'_Y$ 应该是一个只有 $O(1)$ 段的分段五次函数 （$f_Y$ 是三次，求和后变成四次，乘上 $f_d(Y)$ 变成五次，如果不知道具体是几次的话试试就好了），同时它的断点应该就是 $f_a, f_b, f_c$ 的断点的相对位置改变的所有点与 $f_d$ 断点合并的结果，原因大概是当 $f_a, f_b, f_c$ 的断点相对位置不变时我们可以简单刻画出 $f'(Y)$ 的变化。具体证明应该也是可以的，但是比较麻烦。

$f_a(X - Y)$ 的断点会随着 $Y$ 的增加向右移动，$f_c(X + Y)$ 的断点反之，$f_b(X)$ 的断点则不动。那么我们可以枚举每对断点求出它们碰撞的时间，再加上 $f_d$ 的所有断点，来得到 $f_Y$ 的所有断点。对于每一段再跑一次插值即可做到 $O(1)$，但是带一坨常数。