[bzoj 1100] [POI2007]对称轴osi

求简单多边形对称轴的数量. (1 ≤ 数据组数 t ≤ 10, 3 ≤ 顶点 n ≤ 10^5, |坐标| ≤ 10^8) 这是字符串题??!

没有想到比较好的刻画 "轴对称" 这一特征的方法......

找到多边形的中心 (横,纵坐标分别取算术平均), 向每个顶点连线. 以连线长度, 夹角大小为元素, 根据它们的相对顺序构造一个大小为 2n 的环. 由全等三角形的判定方法 (SAS), 我们知道, 对称轴的数量 = 长度为 2n-1 的回文串的数量 / 2.

把多边形的信息压缩为一个环 (序列). 很巧妙.

typedef long double ld;

const int N = 1e5 + 1;

// 省略计算几何模板

Point P[N];
int m, f[4*N];
ld s[4*N];

int manacher()
{
	int j = -1, mx = -1, ans = 0;
	rep (i, 0, m - 1)
	{
		f[i] = mx > i ? min(mx - i, f[2*j - i]) + 1 : 1;
		while (i+f[i] < 2*m && i >= f[i] && !sgn(s[i+f[i]] - s[i-f[i]])) ++f[i];
		if (i + --f[i] > mx) mx = i + f[i], j = i;
		ans += f[i] >= m/2 - 1;
	}
	return ans;
}

int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		Point O;
		rep (i, 0, n)
			scanf("%Lf%Lf", &P[i].x, &P[i].y), O = O + P[i];
		O = O / n;
		rep (i, 0, n) P[i] = P[i] - O;
		P[n] = P[0];
		m = 0;
		rep (i, 0, n)
			s[m++] = Length(P[i]), s[m++] = Angle(P[i], P[i+1]);
		copy(s, s+m, s+m);
		printf("%d\n", manacher());
	}
	return 0;
}