ICPC2017 Asia Regional Tsukuba B Parallel Lines
問題
平面上にm個の点が与えられる。その中から相違なる2n点を選び、n本の線分を作る。(nは自由)
n本の線分のうち、平行であるペアの個数を最大化したい。
そのようなペアの個数の最大値はいくつか。
制約条件
m≦16
座標は絶対値1000以下の整数
解法
実は全探索で間に合う。
(16!は間に合わないが、使える点のうち番号が一番若いものを今使う線分の端点として選ぶとしても全ての場合が尽くされるので、15 * 13 * ... * 3 * 1 で約200万通りだけ。)
自分の解法はbitDPで、dp[bit]をbitの集合の点を使うときのペアの最大値とするようなテーブルを更新するDP.
テーブルを更新するときに入れる集合は全ての線分が平行であるようなものに限定してよくて、
そのような集合は最初に列挙しておく。少し面倒かも。
int n, x[20], y[20]; bool parallel(int i, int j, int k, int l){ ll dx1 = x[i] - x[j]; ll dy1 = y[i] - y[j]; ll dx2 = x[k] - x[l]; ll dy2 = y[k] - y[l]; return dx1 * dy2 == dx2 * dy1; } int num[1 << 16]; int main(){ cin >> n; rep(i, n) cin >> x[i] >> y[i]; //maskの集合で、全て線分が同じ傾きであるときのペアの最大値を列挙 rep(mask, 1 << n){ rep(i, n) rep(j, i) if((mask >> i & 1) && (mask >> j & 1)){ int cnt = 0; rep(k, n) rep(l, k) if((mask >> k & 1) && (mask >> l & 1) && parallel(i, j, k, l)) cnt++; num[mask] = max(num[mask], cnt * (cnt - 1) / 2); } } //求めた集合を使ってDP rep(i, 1 << n) for(int j = i; j; j = j - 1 & i) num[i] = max(num[i], num[j] + num[i ^ j]); cout << num[(1 << n) - 1] << endl; return 0; }