とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

xmas contest 2012 G問題について

ネット環境がよい場所に来たので書きます。
日本語が合っているかはよくわかりませんがどうぞ。

問題概要

平面上の格子点にn個の点があって、凸5角形が何個作れるか。
ただし任意の三点は同一直線上に存在しない
n<=400

解法

求めるのは、5点選んでそれの凸包が5点で構成されるもの。
したがって、5点選んで凸包が4点または3点で構成されるものを数え上げることが出来れば答えを求めることができる。

まず、4点の凸包のものについて考えてみる。
選んだ5点で、「ある3点で三角形を作り、内部に1点、外部に1点存在する」ようなものは2通りある。


f:id:tokoharu-sakura:20121228201400p:plain

次に3点の凸包のあるものについて考えてみる。
これも同様に
選んだ5点で、「ある3点で三角形を作り、内部に1点、外部に1点存在する」ようなものは2通りある。

f:id:tokoharu-sakura:20121228201407p:plain

さらに、「ある3点で三角形を作り、内部に1点、外部に1点存在する」ような5点の選び方をすると、上記のいずれかに当てはまります。
したがって、(「ある3点で三角形を作り、内部に1点、外部に1点存在する」ような5点の選び方 )/ 2を計算すれば良いことになります。

愚直に4重ループを回せば以下のようなシンプルなコード(変数名などは雑)ができます

LL yobi(PII A , PII B) {
	LL ret = (LL)A.second * (LL)B.first - (LL)A.first * (LL)B.second;
	return ret;
} 

LL menseki(PII A , PII B , PII C) {
	LL ret = yobi(A,B) + yobi(B,C) + yobi(C,A);
	if(ret<0) ret = -ret;
	return ret;
}

void solve() {
	int n;
	cin>>n;
	vector<PII> coor;
	for(int i=0; i<n; i++) {
		LL x,y;
		cin>>x>>y;
		coor.push_back(MP(x,y));
	}
	LL ans = (LL)n*(n-1)*(n-2)*(n-3)*(n-4) / 120;
	LL tmp = 0;
	LL cntA = 0;
	for(int i=0; i<n; i++) for(int j=0; j<i; j++) for(int k=0; k<j; k++) {
		int cnt = 0;
		LL total = menseki(coor[i] , coor[j] , coor[k]);
		for(int t=0; t<n; t++) if(t!=i && t!=j && t!=k) {
			LL hikaku = 
				menseki(coor[i] , coor[j] , coor[t])
			 + menseki(coor[j] , coor[k] , coor[t])
			 + menseki(coor[k] , coor[i] , coor[t]);
			if(hikaku==total) cnt++;
		}
		cntA += (LL) cnt * (n-3-cnt) ;
	}
	cout<< ans - cntA/2  <<endl;
}


int main() {
	int t;
	cin>>t;
	for(int i=0; i<t; i++) solve();	
	return 0;
}
 

何分かしたら答えが返ってくると思います。
3点選んだ時の内部の点数の列挙ってどうするのが高速になるんでしょう。
すごいうまい方法があってもよさそうだなぁと思ったので誰か是非教えてください。


ちなみにこんな感じの解法を6角形にしてみた問題に適用させようとしましたが、位置関係の場合分けの時点で多すぎて死亡しました。5角形のうまく行きすぎ感がすごかったです。