ICPC2017 国内予選 H 等積変形

問題

面積の等しい三角形A, Bが与えられる。
三角形Aに対し等積変形（二頂点を固定し、残り一頂点を三角形の面積が変わらないように動かす操作）を繰り返し三角形Aを三角形Bに重ねたい。
必要な操作の最低回数（あるいは4回以内にはできない）を求めよ。

解法

通ったけど正当性が怪しい。
全ての操作は可逆なので三角形Aだけでなく三角形Bも自由に等積変形してよいと考えていい。
三角形に対する操作で意味があるのは

• Aの頂点をBの頂点まで動かして重ねる
• Bの頂点をAの頂点まで動かして重ねる
• Aの頂点とBの頂点を両方動かしてどこかの場所で一致させる

の二通り。これを全部試す。

ソースコード

//幾何のライブラリ部分は略
bool onL(const L &l, const P &p){
	return abs(ccw(l[0], l[1], p)) != 1;
}
int one(G a, G b){
	int ans = inf;
	//a[s]がb[t]に直接重なる
	if(onL(L(a[2], a[2] + a[0] - a[1]), b[2])) return 1;
	
	//a[s]とb[t]をどっかで重ねる
	double c = cross(a[1] - a[0], b[1] - b[0]);
	if(abs(c) > EPS) ans = min(ans, 2);
	return ans;
}
int two(G a, G b){
	int ans = inf;
	for(int s = 1; s < 3; s++) for(int t = 1; t < 3; t++){
		swap(a[s], a[1]); swap(b[t], b[1]);
		//a[s]がb[t]に直接重なる
		if(onL(L(a[1], a[1] + a[0] - a[2]), b[1])){
			P p = a[1];
			a[1] = b[1];
			ans = min(ans, one(a, b) + 1);
			ans = min(ans, one(b, a) + 1);
			//dbg(s, t, ans);
			a[1] = p;
		}
		//a[s]とb[t]をどっかで重ねる
		double c = cross(a[2] - a[0], b[2] - b[0]);
		if(abs(c) > EPS){
			P p = crosspoint(L(a[1], a[1] + a[2] - a[0]), L(b[1], b[1] + b[2] - b[0]));
			P a0 = a[1]; a[1] = p;
			P b0 = b[1]; b[1] = p;
			ans = min(ans, one(a, b) + 2);
			ans = min(ans, one(b, a) + 2);
			//dbg(s, t, ans);
			a[1] = a0; b[1] = b0;
		}
		swap(a[s], a[1]); swap(b[t], b[1]);
	}
	return ans;
}
int three(G a, G b){
	int ans = inf;
	rep(s, 3) rep(t, 3){
		swap(a[s], a[0]); swap(b[t], b[0]);
		//a[s]がb[t]に直接重なる
		if(onL(L(a[0], a[0] + a[1] - a[2]), b[0])){
			P p = a[0];
			a[0] = b[0];
			ans = min(ans, two(a, b) + 1);
			ans = min(ans, two(b, a) + 1);
			//dbg(s, t, ans);
			a[0] = p;
		}
		//a[s]とb[t]をどっかで重ねる
		double c = cross(a[2] - a[1], b[2] - b[1]);
		if(abs(c) > EPS){
			P p = crosspoint(L(a[0], a[0] + a[2] - a[1]), L(b[0], b[0] + b[2] - b[1]));
			P a0 = a[0]; a[0] = p;
			P b0 = b[0]; b[0] = p;
			ans = min(ans, two(a, b) + 2);
			ans = min(ans, two(b, a) + 2);
			//dbg(s, t, ans);
			a[0] = a0; b[0] = b0;
		}
		swap(a[s], a[0]); swap(b[t], b[0]);
	}
	return ans;
}

int main(){
	while(1){
		G a, b;
		rep(i, 3){
			int x, y; if(!(cin >> x >> y)) exit(0);
			a.emplace_back(x, y);
		}
		rep(i, 3){
			int x, y; cin >> x >> y;
			b.emplace_back(x, y);
		}
		int ans = inf;
		ans = min(ans, three(a, b));
		ans = min(ans, three(b, a));
		if(ans >= 5) cout << "Many" << endl;
		else cout << ans << endl;
	}
	return 0;
}