Axes of Symmetry (POI)

2014-12-02 | [Competitive programming]

問題

ここに書いてある。

一言でいうと、多角形の線対称軸の数を求めよという問題。

解法

多角形の各辺について (長さ, 隣の辺とのなす角) を並べた列を考える（これを特徴列と呼ぶ）。 2 つの多角形が一致することと、2 つの多角形に対応する列を適当に回転させることで一致させられることは同値である。

ある軸に対して線対称移動を行うというのは、適当な軸に対して線対称移動を行った後、適切に平行移動、回転を行うことと同じなので、線対称軸を求めるのは「適当に線対称移動した図形を回転させて元の図形と重ねる方法」を求めることと同じになる。

これを求めるには、元の図形に対する特徴列 A と、線対称移動した図形に対する特徴列 B を、B の回転のみによって一致させる方法が何通りあるかを求めればよい。

これは、B をコピーにより 2 倍くらいに伸ばして、A と完全に一致する箇所が何箇所あるか数えるのと同じだから、KMP 法により線形で求められる。

↑を単純に実装すると浮動小数点が出てきてうっとうしいが、辺 ab の次が辺 bc であるときに、(長さ, 隣の辺とのなす角) のかわりに (|b-a|^2, (c-b)*conj(b-a)) を用いてもよい。これは 64bit 整数演算ですべて実行できるため、誤差の心配も一切ない。

コード

#include <cstdio>

#include <complex>

using namespace std;

typedef long long i64;
typedef complex<i64> comp;

int T;
int N;
comp P[100100];
pair<i64, comp> seq[100100], cj[200100];
int fail[100100];

int main()
{
	scanf("%d", &T);
	for (; T--;) {
		scanf("%d", &N);
		for (int i = 0; i < N; ++i) {
			int x, y;
			scanf("%d%d", &x, &y);
			P[i] = comp(x, y);
		}
		P[N] = P[0];
		P[N + 1] = P[1];

		for (int i = 0; i < N; ++i) {
			comp v1 = P[i + 1] - P[i], v2 = P[i + 2] - P[i + 1];
			seq[i] = make_pair(norm(v1), v2 * conj(v1));
			cj[N - i - 1] = cj[2 * N - i - 1] = make_pair(norm(v2), v2 * conj(v1));
		}
		seq[N] = make_pair(-1LL, seq[0].second);

		int p;
		p = fail[0] = -1;

		for (int i = 0; i <= N; ++i) {
			while (p >= 0 && seq[i] != seq[p]) p = fail[p];
			fail[i + 1] = ++p;
		}

		int ret = 0;
		p = 0;

		for (int i = 0; i < 2 * N - 1; ++i) {
			while (p >= 0 && seq[p] != cj[i]) p = fail[p];
			if (++p == N) ++ret;
		}

		printf("%d\n", ret);
	}

	return 0;
}