E: Snuke and Spells - AtCoder Regular Contest 082
点集合が与えられる。部分集合Sが凸包の頂点をなすとき、そのSのスコアをexp(2, (Sの内部と境界にある点の数) - |S|) と定義する。この点のすべてのSについてそのスコアの和を求めよ。
スコアの意味をよく考えてみると、点集合全体の部分集合の数から、凸包にならない部分集合の数を引いたものである。凸包にならないものとは、ある一直線上に並んだ2点以上の部分集合と、1点のみの部分集合、空集合になる。1点と空集合はn + 1を引けばよい。
同一直線状に並んだ2点以上の部分集合は、二重ループを回し、直線のハッシュなどをキーにして、ハッシュの値などに点をどんどん追加していく。その後、得られた直線 (最大で n(n-1)/2 個)に対応する点集合(サイズkとする)について、その中の2点以上の部分集合 2^k - k - 1 の和となる。
最後に2^nから上記の和とn + 1を引けば答え。O(n^2)。
