Coin Slider [JAG Practice Contest for ACM-ICPC Asia Regional 2017 G]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_g

N個の円があり、それぞれ始点(sx[i],sy[i])、終点(tx[i],ty[i])、半径r[i]である。
最初、全て始点にある。
この円を適切な順番で終点に動かす。
動かす過程で他の円と交わってはいけない。
最大何個の円を動かせるか。

前提知識

• bitDP
• 幾何(線分と点との距離)

解法

https://jag2017autumn.contest.atcoder.jp/submissions/1794722

bitDPをする。
dp[mask] := ビットが立っていれば円は終点にあり、立っていないならば始点にある状態を作ることができるか
あとは、そこからの遷移で他の円にぶつからずに移動できるかの判定をするだけ。
この判定は線分と点との距離を測れば良い。
公式解説の図がとても分かりやすい。
移動させたい円iと他のある円jがぶつかるのは、
(円iの始点と終点を結んだ線分と円jの中心点との距離) ＜ (円iの半径) + (円jの半径)
をみたす時である。
これをやって、あとは、ビットが立っている数を数えて最大値が答え。

int N, R[20], SX[20], SY[20], TX[20], TY[20];
int dp[1 << 16];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> R[i] >> SX[i] >> SY[i] >> TX[i] >> TY[i];
 
    dp[0] = 1;
    rep(msk, 0, 1 << N) if (dp[msk]) rep(i, 0, N) if (!(msk & (1 << i))) {
        L l(P(SX[i], SY[i]), P(TX[i], TY[i]));
        vector<P> v; vector<int> r;
        rep(j, 0, N) if (i != j) {
            if (msk & (1 << j)) v.push_back(P(TX[j], TY[j])), r.push_back(R[j]);
            else v.push_back(P(SX[j], SY[j])), r.push_back(R[j]);
        }
 
        int ok = 1, n = v.size();
        rep(j, 0, n) {
            double d = distanceSP(l, v[j]);
            if (d < R[i] + r[j] - EPS) ok = 0;
        }
        if (ok) dp[msk + (1 << i)] = 1;
    }
 
    int ans = 0;
    rep(msk, 0, 1 << N) if (dp[msk]) {
        int c = 0;
        rep(i, 0, N) if (msk & (1 << i)) c++;
        ans = max(ans, c);
    }
    cout << ans << endl;
}