PKU 2684 Polygonal Line Search

• 幾何
• 図形を何らかの形で正規化して比較する
• ここでは始点から各点への長さと角度で正規化している

typedef complex<double> P;
typedef vector<pair<double, double> > Normalized;

bool equals(const Normalized& first, const Normalized& second) {
	if (first.size() != second.size()) {
		return false;
	}

	const double ratio = first[0].first / second[0].first;
	REP(i, first.size()) {
		const double r = first[1].first / second[1].first;
		if (abs(ratio - r) > EPS) {
			return false;
		}
	}

	vector<double> arg0;
	REP(i, first.size()) {
		arg0.push_back(first[i].second - second[i].second - (first[0].second - second[0].second));
	}

	bool ok0 = true;
	REP(i, first.size()) {
		if (!(abs(arg0[i]) < EPS || abs(PI2 - abs(arg0[i])) < EPS)) {
			ok0 = false;
		}
	}
	return ok0;
}

Normalized convert(const vector<P>& polygon) {
	Normalized normalized;
	const P& first = polygon[0];
	for (int i = 1; i < polygon.size(); ++i) {
		const P& p = polygon[i];
		normalized.push_back(make_pair(abs(p - first), arg(p - first)));
	}
	return normalized;
}

int main() {
	for (int n; cin >> n && n; ) {
		vector<pair<Normalized, Normalized> > normalizeds;
		REP(polygonIndex, n + 1) {
			int m;
			cin >> m;
			vector<P> polygon;
			REP(pointIndex, m) {
				double x, y;
				cin >> x >> y;
				polygon.push_back(P(x, y));
			}

			Normalized front = convert(polygon);
			reverse(ALL(polygon));
			Normalized back = convert(polygon);
			normalizeds.push_back(make_pair(front, back));
		}

		for (int i = 1; i <= n; ++i) {
			if (equals(normalizeds[0].first, normalizeds[i].first) || equals(normalizeds[0].first, normalizeds[i].second)) {
				cout << i << endl;
			}
		}
		cout << "+++++" << endl;
	}
}