AOJ 2682 - Polygon Guards

問題文

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

解法

答えは 9 以下なので全探索で間に合う（えぇ…）。
前処理で、ある点に配置したときにどこが見えるようになるかを bit で管理すると判定が O(1) になる。
視線の線分が多角形内部に全部入っているかどうかの判定は適当にやるとハマる。
まず、その線分と多角形の交点を全部求める。
線分の両端から線分の内側にちょっと進んだところが多角形の内部にあるかをまず判定。
交点については、線分の方向ベクトルの2方向にちょっと進んだところが多角形内部にあるかで判定。
この2つをすべてクリアした場合のみ、その点が見える。

AOJ でも 2sec ぐらいかかったので本番で出たらもうちょっと高速化しないとダメかも。

ソースコード

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

// ライブラリ部分は省略

int dfs(polygon const& ps, int i, ll cur_vis, ll used, vector<ll> const& vis) {
    const int n = ps.size();
    if(cur_vis == (1LL << n) - 1) return __builtin_popcountll(used);
    if(i == n) return 9;
    int res = dfs(ps, i + 1, cur_vis, used, vis);
    if(__builtin_popcountll(used) < 8) {
        res = min(res, dfs(ps, i + 1, cur_vis | vis[i], used | (1LL << i), vis));
    }
    return res;
}

int main() {
    int n; cin >> n;
    polygon ps(n);
    for(int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;
        ps[i] = point(x, y);
    }

    vector<ll> vis(n);
    for(int i = 0; i < n; ++i) {
        vis[i] = 1LL << i;
        for(int j = 0; j < n; ++j) {
            if(i == j) continue;
            segment s(ps[i], ps[j]);
            bool check = true;
            for(int k = 0; k < n; ++k) {
                segment t(ps[k], ps[(k + 1) % n]);
                if(!isis_ss(s, t)) continue;
                const auto delta = (ps[j] - ps[i]) / abs(ps[i] - ps[j]) * 0.001;
                for(auto p : is_ss(s, t)) {
                    if(abs(s.a - p) > eps && abs(s.b - p) > eps) {
                        check &= is_in_polygon(ps, p + delta) != 2 && is_in_polygon(ps, p - delta) != 2;
                    }
                }
                check &= is_in_polygon(ps, ps[i] + delta) != 2;
                check &= is_in_polygon(ps, ps[j] - delta) != 2;
            }
            if(check) {
                vis[i] |= 1LL << j;
            }
        }
    }

    cout << dfs(ps, 0, 0, 0, vis) << endl;
}

感想

この問題みたいな多角形だと、n / 4 以下でできることが示せるらしい。
一般の多角形なら n / 3 とのこと。
たしかに多角形を三角形 or 四角形で分割することを考えるとそんな気もする。