Parallel Lines [ICPC2017アジア予選 B]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ICPCOOC2017&pid=B

M点ある（Mは偶数）。
i番目の座標は(X[i], Y[i])。
全ての点を2点でマッチングさせて、直線を引く。
平行である線の組の最大個数は？

前提知識

• bitDP、および、O(3^N)の部分集合の列挙

解法

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2650871&cid=ICPCOOC2017

M ≦ 16といういかにもな制約があるので、ここから考える。
制約的にはO(2^M)という感じ。
bitDPだろうなぁと考えていくとDPできる。
　
「dp1[msk] := 部分集合mskを全てマッチングさせて、全て平行な直線が作れるか」
これをbitDPを使って解決していく。
このためにもう1つDPを用意する。
「dp2[msk] := 部分集合mskを全てマッチングさせた時に作れる全て平行な直線の傾きの集合」
これを更新しながらdp2を更新していく。
具体的には

• dp1[msk] = 1をチェックする
• mskから2点a,bを選び、その二点を抜いた部分集合をnmskとする
• 「dp1[nmsk] == 1であり、点a,bの直線の傾きがdp2[nmsk]に含まれる」ときはdp1[msk] = 1

これを順にやっていく。
　
これで答えのbitDPの用意が整った。
「dp3[msk] := 部分集合mskを使って出来る平行線の組の個数の最大値」
これはmskを2つに分けて足し合わせることで更新していく。
具体的にはO(3^N)の部分集合の列挙をやる
dp3[(1<

int M, X[20], Y[20];
int dp1[1 << 16];
set<pair<int, int>> dp2[1 << 16];
int dp3[1 << 16];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> M;
    rep(i, 0, M) cin >> X[i] >> Y[i];
 
    dp1[0] = 1;
    rep(a, 0, M) rep(b, a + 1, M) {
        int msk = (1 << a) + (1 << b);
        dp1[msk] = 1;
        dp2[msk].insert({X[b] - X[a], Y[b] - Y[a]});
    }
 
    rep(msk, 0, 1 << M) {
        if (__builtin_popcount(msk) % 2 == 1) continue;
        if (__builtin_popcount(msk) <= 3) continue;
        rep(a, 0, M) if (msk & (1 << a)) rep(b, a + 1, M) if (msk & (1 << b)) {
            int nmsk = msk - (1 << a) - (1 << b);
            if (!dp1[nmsk]) continue;
             
            int dx = X[a] - X[b];
            int dy = Y[a] - Y[b];
 
            fore(p, dp2[nmsk]) {
                if (dx * p.second == dy * p.first) {
                    dp1[msk] = 1;
                    dp2[msk].insert(p);
                }
            }
        }
    }
 
    rep(msk, 0, 1 << M) if(dp1[msk]) {
        int c = __builtin_popcount(msk)/ 2;
        dp3[msk] = c * (c - 1) / 2;
    }
 
    rep(msk, 0, 1 << M) {
        for (int i = msk; i >= 0; i--) {
            i &= msk;
 
            dp3[msk] = max(dp3[msk], dp3[i] + dp3[msk - i]);
        }
    }
 
    int ans = dp3[(1 << M) - 1];
    cout << ans << endl;
}