AOJ 2569 - Putter

問題文

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

解法

線分の通り方を n! 通り全探索する。
ある線分を通る時に、その線分で点を鏡写しにしていけば、直線がそれらの線分を貫くかどうか、という問題になる。
この判定は角度（厳密にはベクトル）で行う。
始点から、ある線分を通るような範囲をベクトルで表すことにする。
つまり、始点から線分の端点へのベクトル2つを、より反時計回り方向にある方とそうでない方で管理する。
すべての範囲が共通部分を持てばOK。
そのために、反時計回りにある方のベクトルだけを考えて、それらの中でもっとも時計回り方向にあるものを考える（時計回りの方は逆）。
こうして得られた2つのベクトルが、反時計回りのほうがちゃんと反時計回りの方にあるならOK。
ここまでの計算は全部外積だけでできる。

ただし、反時計回りのやつを時計回りに、時計回りのやつを反時計回りの方に寄せていった結果、最終的に寄せた大きさが180度を超えて条件合致してしまうケースがある。
なので、最も（反）時計まわりにあるものを考えるというよりは、ベクトルの範囲を1つずつ見ていって、常に共通部分を持つもの、とする。
convex polygon なのでこれでちゃんと判定可能（今条件合致していて、次に鏡写しにしたときのベクトルの範囲を考えたときに、範囲が大きく変動して、偶然条件合致と判定されないということ）。

ソースコード

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

using ld = double;
using point = std::complex<ld>;
using polygon = std::vector<point>;

struct line {
    line() : a(0, 0), b(0, 0) {}
    line(point a_, point b_) : a(a_), b(b_) {}
    point a, b;
};

ld dot(point const& a, point const& b) {
    return std::real(std::conj(a) * b);
}
ld cross(point const& a, point const& b) {
    return std::imag(std::conj(a) * b);
}

point proj(line const& l, point const& p) {
    ld t = dot(p - l.a, l.a - l.b) / std::norm(l.a - l.b);
    return l.a + t * (l.a - l.b);
}

point reflect(line const& l, point const& p) {
    return p + (proj(l, p) - p) * 2.0;
}

point read_point() {
    ld x, y; cin >> x >> y;
    return point{x, y};
}

int main() {
    int n;
    while(cin >> n, n) {
        const auto sp = read_point();
        polygon ps;
        for(int i = 0; i < n; ++i) {
            ps.emplace_back(read_point());
        }

        vector<int> ord(n);
        iota(begin(ord), end(ord), 0);
        int ans = 0;
        do {
            auto ts = ps;
            vector<point> lvs, rvs;
            for(auto i : ord) {
                const auto a = ts[i], b = ts[(i + 1) % n];
                lvs.push_back(a + (b - a) / abs(b - a) * 1e-6 - sp);
                rvs.push_back(b + (a - b) / abs(b - a) * 1e-6 - sp);
                if(cross(rvs.back(), lvs.back()) < 0) swap(lvs.back(), rvs.back());
                for(int j = 0; j < n; ++j) {
                    if(j == i || (i + 1) % n == j) continue;
                    ts[j] = reflect(line{a, b}, ts[j]);
                }
            }
            auto lv = lvs[0], rv = rvs[0];
            bool check = true;
            for(int i = 1; i < n; ++i) {
                if(cross(lv, lvs[i]) <= 0) swap(lv, lvs[i]);
                if(cross(rv, rvs[i]) >= 0) swap(rv, rvs[i]);
                check &= cross(rv, lv) >= 0;
            }
            ans += check;
        } while(next_permutation(begin(ord), end(ord)));

        cout << ans << endl;
    }
}

感想

（反）時計回り側のベクトルを全部統合してから判定してて最初死んでいた。
多分本番だと無限に悩むやつ。そして多分通らないまま終わる。悲しいね。