Codeforces Round #330 (Div. 1) C. Edo and Magnets

問題

codeforces.com

解法

各マグネットの中心(重心)座標しか興味ないので入力値からそれを求めます。この時, double で管理しようとすると不幸になるのですべての座標が 2 倍されてると考えて座標が整数になるようにしましょう。

この重心座標については, どう考えても毎回 左端/右端/上端/下端 のいずれかにある頂点を取り除いていくことが最適です。

ということで, 通りの取り除き方を試しながら頑張れば良いです。
これ k = 50 程度までなら解けますよね, 多分。(通り調べれば良いので)

const ll INF = 1ll<<60;
const int MAXN = 100100;
ll ans = INF;
int n, k;
bool used[MAXN];
// 0:小さい順にx 1:大きい順にx 2:小さい順にy 3:大きい順にy
pair<ll, int> P[4][MAXN];

void dfs(int cnt) {
    if (cnt == k) {
        ll tmp[4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < n; j++) if (!used[P[i][j].second]) {
                tmp[i] = P[i][j].first;
                break;
            }
        }
        ll dx = tmp[1]-tmp[0];
        ll dy = tmp[3]-tmp[2];
        dx = (dx+1)/2;
        dy = (dy+1)/2;
        dx = max(dx, 1ll);
        dy = max(dy, 1ll);
        ans = min(ans, dx*dy);
        return;
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < n; j++) {
            if (!used[P[i][j].second]) {
                used[P[i][j].second] = true;
                dfs(cnt+1);
                used[P[i][j].second] = false;
                break;
            }
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> k;
    if (n <= k) {
        cout << 1 << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) {
        ll x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int j = 0; j < 2; j++) {
            P[j][i] = make_pair(x1+x2, i);
        }
        for (int j = 2; j < 4; j++) {
            P[j][i] = make_pair(y1+y2, i);
        }
    }
    for (int i = 0; i < 4; i++) sort(P[i], P[i]+n);
    reverse(P[1], P[1]+n);
    reverse(P[3], P[3]+n);
    dfs(0);
    cout << ans << endl;
    return 0;
}