AtCoder ARC #082 : E - ConvexScore

割と苦戦した。
https://beta.atcoder.jp/contests/arc082/tasks/arc082_c

問題

２次元座標中に異なる頂点N個が与えられる。
このうちいくつかの点を選んで凸な多角形Sを構成したとする。
元のN点のうち、Sに含まれる頂点をn個とするとき、Sのスコアは2^(n-|S|)となる。

各Sに対し、スコアの総和を求めよ。

解法

N個の頂点のうち、いくつかを選びその凸包を取ることを考える。
各頂点は選ぶ選ばないの２択なので全体で2^Nの選び方ができる。
凸包の内部の点は選んでも選ばなくても凸包の形状は変わらないが、その凸包を生成する選び方の組み合わせを倍にすることができると言える。

ここから、この問題は以下のように言い換えることができる。
「N個のうち各頂点を選ぶ選ばないの２択で、計2^Nの選び方をしたとき、それらの凸包の面積が正となるものは何通りか。」

全体の2^N通りから、以下のものを引こう。

• 選ぶ頂点が3点未満のケース通り
• 同一直線上の頂点から3点以上選ぶケース

int N;
ll X[202],Y[202];
ll mo=998244353;
int did[202][202];
ll p2[202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	
	ll ret=1;
	p2[0]=1;
	FOR(i,N) p2[i+1]=p2[i]*2%mo;
	
	ret=(p2[N]+mo-1-N-N*(N-1)/2)%mo;
	
	FOR(y,N) FOR(x,y) if(did[y][x]==0) {
		vector<int> V;
		V.push_back(x);
		V.push_back(y);
		FOR(i,N) if(i!=x && i!=y) if((X[i]-X[x])*(Y[y]-Y[x])-(X[y]-X[x])*(Y[i]-Y[x])==0) V.push_back(i);
		FORR(a,V) FORR(b,V) did[a][b]=1;
		r=V.size();
		if(r>=3) ret=(ret+mo-p2[r]+r+r*(r-1)/2+1)%mo;
	}
	
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

スコアの意味を考えるのが重要な問題。
FFTに見せかけてFFTじゃないの流行ってるの？