xmas contest 2012 G問題について

問題概要

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

解法

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

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

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

さらに、「ある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角形のうまく行きすぎ感がすごかったです。