TopCoder SRM 585 Div2 Hard EnclosingTriangleColorful

さてDiv2 Hard。今回はさほど難しくないな。
http://community.topcoder.com/stat?c=problem_statement&pm=12694

問題

(0,0)-(M,M)で構成される正方形がある。
正方形の辺上、上辺・右辺・下辺・左辺はそれぞれ青・緑・赤・黄色の色が点いている。
正方形の内部には、N個(<=50)の黒点がある。

辺上から異なる色の点を３つ選んだとき、その３点で作れる三角形の内部または辺上に黒点がすべて含まれるような組み合わせの数を答えよ。

解法

M<=300のため、辺上の点は1200程度。よって点を３つ選ぶO(M^3)解法は採用できない。
まず、辺上の任意の２点を結んだ時、各黒点がその辺上または右側にあるかどうかをベクトルの外積で求める。これはO(NM^2)なので何とか処理できる。

あとは、辺上の任意の２点を選び、すべての黒点が右側にある点の組み合わせに対してのみ、３点目を列挙すればよい。
先に２点選んだ時点で多くのケースで黒点が左側に来てしまうため、３点目を選ぶ回数を削減できる。
また、同じ色の選択を避けることで高速化している。

int okok[1200][1200];

class EnclosingTriangleColorful {
	int N;
	vector<int> X,Y;
	vector<pair<int,int> > V;
	public:
	
	int check(int p1,int p2) {
		int i;
		FOR(i,N) {
			if((V[p2].second-V[p1].second)*(X[i]-V[p1].first)-
				(V[p2].first-V[p1].first)*(Y[i]-V[p1].second)<0) return 0;
		}
		return 1;
	}
	
	int getNumber(int m, vector <int> x, vector <int> y) {
		
		N=x.size();
		V.clear();
		int x1,x2,y1,y2,i,j,k,r=0;
		
		ZERO(okok);
		X=x;Y=y;
		
		for(i=1;i<m;i++) V.push_back(make_pair(i,m));  // top 
		for(i=1;i<m;i++) V.push_back(make_pair(m,m-i));// right
		for(i=1;i<m;i++) V.push_back(make_pair(m-i,0));// bottom
		for(i=1;i<m;i++) V.push_back(make_pair(0,i));// left
		
		FOR(x1,V.size()) FOR(x2,V.size()) {
			if(V[x1].first==V[x2].first && (V[x1].first==0 || V[x1].first==m)) continue;
			if(V[x1].second==V[x2].second && (V[x1].second==0 || V[x1].second==m)) continue;
			okok[x1][x2]=check(x1,x2);
		}
		
		m--;
		FOR(i,m) FOR(j,m) if(okok[i][j+m]) FOR(k,m) r+=okok[j+m][k+2*m]&okok[k+2*m][i];
		FOR(i,m) FOR(j,m) if(okok[i][j+m]) FOR(k,m) r+=okok[j+m][k+3*m]&okok[k+3*m][i];
		FOR(i,m) FOR(j,m) if(okok[i][j+2*m]) FOR(k,m) r+=okok[j+2*m][k+3*m]&okok[k+3*m][i];
		FOR(i,m) FOR(j,m) if(okok[i+m][j+2*m]) FOR(k,m) r+=okok[j+2*m][k+3*m]&okok[k+3*m][i+m];
		
		return r;
	}
};

まとめ

すんなり解けて良かった。
Div1 Hardは色制限がないうえにmが大きいけど、どう解くんだろうな。