P6143 [USACO20FEB]Equilateral Triangles P & ZLOJ 练习70 C

written on 2022-08-22

有关曼哈顿距离的题目，同时涉及斜对角线前缀和。

此题要求寻找曼哈顿距离意义下的等边三角形，那么涉及曼哈顿距离，我们可以想到，到一个点曼哈顿距离相等的点构成了一个菱形，并且这一块是可以用前缀和快速计算的。

这题的启示就是如果题目与曼哈顿距离意义下的等边三角形有关的话，那么我们可以考虑定义该意义下等边三角形的外心，即到三点距离均相等的点。曼哈顿距离有一个很好的性质，也就是两点之间的路径不唯一，对于一条曼哈顿路径，任意平移后可能得到另一条合法路径。那么一个合法的等边三角形一定是类似于这样的形状：

（借一下@ix35的图）

那么固定两点 \(A,B\) 后，\(C\) 的个数就可以用前缀和来计算了，然后注意去重，旋转原图，就能够得到答案了。