AtCoder Regular Contest 082 E - ConvexScore

http://arc082.contest.atcoder.jp/tasks/arc082_c

問題概要

二次元平面上のN個の点が与えられる。これらの点の部分集合Sであって凸多角形をなすものについて考える。このようなSの凸包に対し、凸包の周上の点と内部の点の数の合計をnとし、2n-|S|をSのスコアとする。すべてのSの合計を求めよ。

N <= 200

解法

実は各点を選ぶ・選ばないの2N通りの全列挙が、スコア計算と実質同じことをやっている。例えば凸包Sに対して内部の点が3個あった場合スコアは23=8になるが、2Nの列挙においてこれに対応するのは「Sの点がすべて選ばれる+内部の点が任意に選ばれる+他は選ばれない」というパターンである。これは内部の点を選ぶ・選ばないで23=8通りであり、スコアと一致する。なので基本的には2Nを計算すればスコアの合計は全部数えたことになる。あとはそこから余分な選び方を引けばよい。余分な選び方は

  • 選ばれる点が1個以下の場合
  • 選ばれる点の凸包が線分になる場合

の2パターンがある。前者も後者も明らかに凸多角形をなさないので、スコア計算対象から外れるためである。

ここで前者は明らかに(N+1)通りある。後者は同じ直線に載っている点集合の数をxとすると2x通りある(前者との重複を引くと2x-x-1通り)。これらを2Nから引けばそれが答えになる。後者の求め方についてはまずありうる直線を列挙しその直線上に乗っている点を数えると、直線列挙でO(N2)(ありうる2点の組合せの列挙)、直線に乗っている点の探索でO(N)の合わせてO(N3)で答えが求まる。

感想

いやわからんわ

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
 
long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}
 
void main() {
    auto N = readln.chomp.to!int;
    auto X = new long[](N);
    auto Y = new long[](N);
    foreach (i; 0..N) {
        auto s = readln.split.map!(to!long);
        X[i] = s[0];
        Y[i] = s[1];
    }
 
    bool line(int i, int j, int k) {
        if (X[i] == X[j]) return X[i] == X[k];
        if (Y[i] == Y[j]) return Y[i] == Y[k];
        if (X[i] == X[k]) return X[i] == X[j];
        if (Y[i] == Y[k]) return Y[i] == Y[j];
        return (Y[k] - Y[i]) * (X[j] - X[i]) == (Y[j] - Y[i]) * (X[k] - X[i]);
    }
 
    const long MOD = 998244353;
    auto used = new bool[][](N, N);
    long ans = 1 + N;
 
 
    foreach (i; 0..N) {
        foreach (j; i+1..N) {
            if (used[i][j])
                continue;
            
            long cnt = 2;
            int[] v = [i, j];
 
            foreach (k; j+1..N) {
                if (used[i][k] || !line(i, j, k))
                    continue;
                cnt += 1;
                v ~= k;
            }
 
            foreach (a; 0..v.length)
                foreach (b; a+1..v.length)
                    used[v[a]][v[b]] = true;
 
            ans += powmod(2, cnt, MOD) - cnt - 1;
            ans %= MOD;
        }
    }
 
    ans = powmod(2, N, MOD) - ans;
    ans = (ans % MOD + MOD) % MOD;
    ans.writeln;
}