Loj 3266 Equilateral Triangles

Posted on | Views:

曼哈顿距离与切比雪夫距离的转化.

将坐标系旋转 $\frac \pi 4$ ,每个点的坐标 $(x,y)$ 就变成了 $(x+y,x-y)$ .

此时原来的曼哈顿距离变成了切比雪夫距离 $\max(|x_1-x_2|,|y_1-y_2|)$ ,三个点形成正三角形需要满足
$$
\max(|x_1-x_2|,|y_1-y_2|)=\max(|x_1-x_3|,|y_1-y_3|)=\max(|x_2-x_3|,|y_2-y_3|)
$$
通过一定的观察可以发现,这三个点中存在两个点的 $x$ 相同,或存在两个点的 $y$ 相同.

证明:若 $x$ 均不相同,可以假定有 $x_1>x_2>x_3$ .

则 $x_1-x_3>x_1-x_2,x_1-x_3>x_2-x_3$ .可知 $|y_1-y_2|=|y_2-y_3|$ .

若 $y$ 也均不相同,则 $|y_1-y_3|>|y_1-y_2|$ ,而 $|x_1-x_3|>|x_1-x_2|$ ,对应 $\max$ 不可能相等.

先枚举两个 $x$ 相同的点 $(a,b),(a,c)$ ,满足 $b<c$ ,考虑计算有多少个点能和它们形成正三角形.

此时 $3$ 个 $\max$ 的值都是 $c-b$ ,可以得出另外一个点只可能是在 $x$ 距离差上取得 $\max$ .

即,统计满足 $x=a\pm(c-b),b\le y\le c$ 的 $(x,y)$ 的数目即可.

再枚举两个 $y$ 相同的点 $(b,a),(c,a)$ ,满足 $b<c$ ,同理计算贡献.

为了不与枚举 $x$ 时贡献重复,统计 $b<x<c,y=a\pm (c-b)$ 的 $(x,y)$ 的数目即可.

时间复杂度 $O(n^3)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(ll x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(ll x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 600 + 10;
int n, p[N][N], t[N][N], row[N][N], col[N][N];
char buf[N];
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", buf + 1);
		for (int j = 1; j <= n; ++j)
			if (buf[j] == '*')
				t[i + j][i - j + n] = 1; 
	}
	n <<= 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
		{
			row[i][j] = row[i][j - 1] + t[i][j];
			col[i][j] = col[i][j - 1] + t[j][i];
		}
	ll ans = 0;
	for (int a = 1; a <= n; ++a)
		for (int b = 1; b <= n; ++b) if (t[a][b])
			for (int c = b + 1; c <= n; ++c) if (t[a][c])
			{
				int d = a + (c - b);
				if (d <= n)
					ans += row[d][c] - row[d][b - 1];
				d = a - (c - b);
				if (d >= 1)
					ans += row[d][c] - row[d][b - 1];
			}
	for (int a = 1; a <= n; ++a)
		for (int b = 1; b <= n; ++b) if (t[b][a])
			for (int c = b + 1; c <= n; ++c) if (t[c][a])
			{
				int d = a + (c - b);
				if (d <= n)
					ans += col[d][c - 1] - col[d][b];
				d = a - (c - b);
				if (d >= 1)
					ans += col[d][c - 1] - col[d][b];
			}
	write(ans, '\n');
	return 0;
}