题解 P6143 [USACO20FEB]Equilateral Triangles P

题目大意：

给一个 \(N\times N\) 的方阵，里面有若干个点，问这些点在曼哈顿距离意义下能构成多少个等边三角形？

数据范围：\(1\le N\le 300\) .

知识储备：前缀和，曼哈顿距离

题目难度：提高+/省选-

解析：

（曼哈顿距离与切比雪夫距离的互相转化是关键思想。）

先构造几个等边三角形，不难发现有一条边一定与坐标轴成 \(45^\circ\) 度角。固定这条边找第三点，发现第三点一定在以这条边为边长的正方形上，且在这条边的对边。比如对于 \(A(0,2),B(2,0)\) ，若 \(C\) 在 \(AB\) 上方，能构成等边三角形的 \(C\) 只能在 \((4,2),(3,3),(2,4)\) 这些位置。这个结论可以通过曼哈顿距离转切比雪夫距离更加方便的得出。

有了这个结论，我们可以通过前缀和处理每个斜线上的点数，这样对于每个斜边 \(AB\) 都可以 \(O(1)\) 算出满足条件的 \(C\) 。对两种斜线都要算一次，同时也要注意去掉重复情况，剩下的简单枚举即可。

时间复杂度：\(O(N^3)\) .