topcoder SRM365 Div2 Hard HittingPerfectTarget

問題URL : https://community.topcoder.com/stat?c=problem_statement&pm=7575

問題概要

2つの凸多角形p1,p2が与えられる．
格子点にダーツを投げるゲームをする．各格子点に刺さる確率は一様である．
p1とp2に包含されている格子点にダーツが刺さる確率を求めよ．

解法

まず，[-101, 101]^2の範囲でp1に包含されない格子点を全列挙することを考える．
これは以下の深さ優先探索(DFS)を行うことで計算可能である．
格子点(-101,-101)からスタートする．
現在，格子点uにいるとし，vをuに隣接する格子点とする．
vがp1の辺上にある，または，線分uvとp1の辺が交差するならば何もしない．
そうでなければvに移動する．
DFSが終了したときに訪問済みの格子点がp1に包含されない格子点となる．

p2についても同様に包含される格子点を全列挙する．
あとは，どちらのDFSでも未訪問の格子点を数えて201^2で割れば求める確率が計算できる．

コード

typedef complex<double> P;

// 許容する誤差ε
#define EPS (1e-10)

// 内積 (dot product) : a・b = |a||b|cosΘ
double dot(P a, P b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}

// 外積 (cross product) : a×b = |a||b|sinΘ
double cross(P a, P b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

// aからbに向かって, 1 -> 右, -1 -> 左, 2 -> aの真後ろ, -2 -> bよりも奥の前, 0 -> 線分ab上に存在
int ccw(P a, P b, P c) {
    P d = b - a;
    c -= a;
    double cr = cross(d, c);
    if(cr < -EPS) { return 1; }
    if(cr > EPS) { return -1; }
    if(dot(d, c) < -EPS) { return 2; }
    if(norm(d) < norm(c) - EPS) { return -2; }
    return 0;
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
int is_intersected_ls(P a1, P a2, P b1, P b2) {
    return ccw(a1, a2, b1) * ccw(a1, a2, b2) <= 0 &&
           ccw(b1, b2, a1) * ccw(b1, b2, a2) <= 0;
}

namespace std {
bool operator <(const P &a, const P &b) {
    if(a.real() != b.real()) return a.real() < b.real();
    return a.imag() < b.imag();
}
}

int ccw2(P p, P a, P b) {
    a -= p;
    b -= p;
    if(cross(a, b) > EPS) return 1;
    if(cross(a, b) < -EPS) return -1;
    if(dot(a, b) < -EPS) return 2;
    if(norm(b) - norm(a) > EPS) return -2;
    return 0;
}

vector<P> convex_hull(vector<P> ps) {
    int n = ps.size(), k = 0;
    sort(ps.begin(), ps.end());
    vector<P> ch(2 * n);
    for(int i = 0; i < n; ch[k++] = ps[i++]) while(k >= 2 && ccw2(ch[k - 2], ch[k - 1], ps[i]) <= 0 && ccw2(ch[k - 2], ch[k - 1], ps[i]) != -2) --k;
    for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) while(k >= t && ccw2(ch[k - 2], ch[k - 1], ps[i]) <= 0 && ccw2(ch[k - 2], ch[k - 1], ps[i]) != -2) --k;
    ch.resize(k - 1);
    return ch;
}


struct HittingPerfectTarget {
    vector<int> x1;
    vector<int> y1;
    vector<int> x2;
    vector<int> y2;

    bool inside(int y, int x) {
        return -101 <= y && y <= 101 && -101 <= x && x <= 101;
    }
    bool check(P a, P b, vector<P> &v) {
        int n = v.size();
        rep(i, v.size()) {
            if(ccw(v[i], v[(i + 1) % n], a) == 0) return false;
            if(is_intersected_ls(v[i], v[(i + 1) % n], a, b)) return false;
        }
        return true;
    }

    void dfs(int x, int y, vvint &ret, vector<P> &v) {
        if(ret[x + 101][y + 101]) return;
        ret[x + 101][y + 101] = 1;
        int dd[] = {0, 1, 0, -1, 0};
        rep(i, 4) {
            int yy = y + dd[i];
            int xx = x + dd[i + 1];
            if(inside(yy, xx) && check(P(xx, yy), P(x, y), v)) {
                dfs(xx, yy, ret, v);
            }
        }
    }
    vvint func(vint &x, vint &y) {
        int n = x.size();
        vector<P> v(n);
        rep(i, n) v[i] = P(x[i], y[i]);
        vvint ret;
        initvv(ret, 203, 203);
        v = convex_hull(v);
        dfs(-101, -101, ret, v);
        return ret;
    }

    double getProbability(vector<int> _x1, vector<int> _y1, vector<int> _x2, vector<int> _y2) {
        x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2;
        vvint res1 = func(x1, y1);
        vvint res2 = func(x2, y2);
        double cnt = 0;
        rep(i, 203) {
            rep(j, 203) {
                if(res1[i][j] == 0 && res2[i][j] == 0) {
                    cnt += 1;
                }
            }
        }
        return cnt / 201 / 201;
    }
};

コメント

幾何は面倒