AOJ 1623 等積変形 (Equivalent Deformation)

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1623&lang=jp

解法

点を合わせる順番と対応を全部試して探索するだけで解ける．
点を合わせるときは，直接合わせられる場合は直接合わせればよいし，そうでない場合は残りの2点のどちらかを適切に移動させてから合わせればよい．このとき2点のどちらを選ぶかは両方試す．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
using point = complex<ld>;

constexpr ld eps = 1e-8;

struct line {
    point a, b;
};

bool eq(ld a, ld b) {
    return std::abs(a - b) < eps;
}

ld cross(point a, point b) {
    return imag(conj(a) * b);
}

bool isis_ll(point v1, point v2) {
    return !eq(cross(v1, v2), 0);
}

point is_ll(line s, line t) {
    point sv = s.b - s.a, tv = t.b - t.a;
    return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

int main() {
    vector<int> x1(3), y1(3);
    while(cin >> x1[0] >> y1[0]) {
        for(int i = 1; i < 3; ++i) cin >> x1[i] >> y1[i];
        vector<int> x2(3), y2(3);
        for(int i = 0; i < 3; ++i) cin >> x2[i] >> y2[i];

        function<int(int, vector<int>, vector<point>, int)> dfs = [&] (int i, vector<int> match, vector<point> ps, int step) {
            if(step >= 5 || i == 3) return step;
            auto vec = point(x2[match[i]], y2[match[i]]) - ps[i];
            auto p2 = ps[(i + 1) % 3], p3 = ps[(i + 2) % 3];
            auto vec2 = p2 - p3;
            if(!isis_ll(vec, vec2)) {
                ps[i] = point(x2[match[i]], y2[match[i]]);
                return dfs(i + 1, match, ps, step + 1);
            } else {
                int res = 5;
                {
                    auto tmp_ps = ps;
                    line l1{p2, p2 + ps[i] - p3};
                    line l2{p3, p3 + vec};
                    auto pp = is_ll(l1, l2);
                    tmp_ps[(i + 1) % 3] = pp;
                    tmp_ps[i] = point(x2[match[i]], y2[match[i]]);
                    res = min(res, dfs(i + 1, match, tmp_ps, step + 2));
                }
                {
                    auto tmp_ps = ps;
                    line l1{p3, p3 + ps[i] - p2};
                    line l2{p2, p2 + vec};
                    auto pp = is_ll(l1, l2);
                    tmp_ps[(i + 2) % 3] = pp;
                    tmp_ps[i] = point(x2[match[i]], y2[match[i]]);
                    res = min(res, dfs(i + 1, match, tmp_ps, step + 2));
                }
                return res;
            }
        };

        vector<int> ord(3);
        iota(ord.begin(), ord.end(), 0);
        int ans = 5;
        do {
            vector<int> match(3);
            iota(match.begin(), match.end(), 0);
            do {
                vector<point> ps(3);
                for(int i = 0; i < 3; ++i) ps[i] = point(x1[ord[i]], y1[ord[i]]);
                ans = min(ans, dfs(0, match, ps, 0));
            } while(next_permutation(match.begin(), match.end()));
        } while(next_permutation(ord.begin(), ord.end()));

        if(ans == 5) cout << "Many" << endl;
        else         cout << ans << endl;
    }
}

感想

こういうの，本番だと難しく見えるんですよね…．