TopCoder SRM 679 Div1 Medium RedAndBluePoints

本番方針は立ったものの時間切れ。バグも色々作りこんだので、どのみち間に合わなかったかな…。
https://community.topcoder.com/stat?c=problem_statement&pm=14117

問題

２次元座標上で、青い点B個と赤い点R個の座標が与えられる。
各頂点の位置は重ならず、かつ３頂点以上が同一直線上に来ることはない。

この座標上において赤い点を１つも含まない凸図形を作るとき、青い点を最大何個含めるものが作れるか。

解法

青い点で構成される凸包を少しずつ広げていくことを考える。
まず以下の前処理を行っておこう。
三角形と頂点の内外判定でO(B^4*(B+R))なので十分間に合う。

• 凸包を求める定番処理として、青い点をX座標順でソートしておく。
• 青い点３点で構成される三角形について：
  • 赤い点が１個でも含まれてしまうことはないか判定する
  • 青い点が内部に何個含まれるか計算する

あとは以下の２変数を更新していく。
up(a,b,c) := (左端を頂点a,右端を頂点cとした凸包でaとcが辺で結ばれており、他の点はすべてa-cを結んだ上側にある。またbの一つ左側の点はcである)ような凸包に含まれる最大青点数。
down(a,b,c) := 「他の点はすべてa-cを結んだ下側にある」以外up(a,b,c)と同じ。

cより右側にある頂点dについて、dを凸包に追加することで上記２変数を更新可能か考える。
まず、a,c,dで構成される三角形領域を凸包に追加したいので、そこに赤点が含まれるなら追加不可。

• b→cを結ぶ辺よりb→dを結ぶ辺が右側にあるならdを追加可能でup(a,c,d)はup(a,b,c)に対しd及び三角形a,c,d内部の青点数分多くなる。
• b→cを結ぶ辺より〃左側にあるならdを追加可能でdown(a,c,d)はdown(a,b,c)に対し〃

upとdownを求めたら、上に凸な凸包と下に凸な凸包をくっつけた凸包を作ることを考えよう。
左端をa、右端をbとする凸包は、up(a,x,b)とdown(a,y,b)のうちx→yを結ぶ辺よりx→bを結ぶ辺が左側を向いているなら結合可能で、内部の青点はa,bを二重カウントしてる分を考慮してup(a,x,b)+down(a,y,b)-2となる。
a,b,x,yを総当たりして上記値の最大値を求めよう。

int NG[51][51][51];
int INS[51][51][51];
int UP[51][51][51];
int LO[51][51][51];
vector<ll> BX,BY;
ll side[51][51][51];

ll cr(ll x1,ll y1,ll x2,ll y2) {
	ll v=x1*y2-x2*y1;
	if(v>0) return 1;
	if(v<0) return -1;
	return 0;
}

int inside(ll x,ll y,int a,int b,int c) {
	int num=0;
	num += cr(x-BX[a],y-BY[a],BX[b]-BX[a],BY[b]-BY[a]);
	num += cr(x-BX[b],y-BY[b],BX[c]-BX[b],BY[c]-BY[b]);
	num += cr(x-BX[c],y-BY[c],BX[a]-BX[c],BY[a]-BY[c]);
	return abs(num)==3;
}

class RedAndBluePoints {
	public:
	
	int find(vector <int> bx, vector <int> by, vector <int> rx, vector <int> ry) {
		int B=bx.size(), R=rx.size();
		if(B<3) return B;
		
		int ret=2;
		int a,b,c,d,x,y;
		vector <pair<int,int>> P;
		FOR(a,B) P.push_back({bx[a],by[a]});
		sort(P.begin(),P.end());
		BX.clear();
		BY.clear();
		FOR(a,B) BX.push_back(P[a].first),BY.push_back(P[a].second);
		
		FOR(a,B) FOR(b,B) FOR(c,B) {
			NG[a][b][c]=INS[a][b][c]=0;
			side[a][b][c]=(BX[b]-BX[a])*(BY[c]-BY[a])-(BY[b]-BY[a])*(BX[c]-BX[a]);
			FOR(x,R) NG[a][b][c] |= inside(rx[x],ry[x],a,b,c);
			FOR(x,B) INS[a][b][c] += inside(BX[x],BY[x],a,b,c);
		}
		memset(UP,0xcf,sizeof(UP));
		memset(LO,0xcf,sizeof(LO));
		FOR(b,B) FOR(a,b) UP[a][a][b]=LO[a][a][b]=2;
		for(x=2;x<B;x++) {
			FOR(a,x) FOR(b,x) if(a!=b&&NG[a][b][x]==0) FOR(c,x) if(b!=c) {
				if(side[c][b][x]<0) UP[a][b][x]=max(UP[a][b][x],UP[a][c][b]+1+INS[a][b][x]);
				else LO[a][b][x]=max(LO[a][b][x],LO[a][c][b]+1+INS[a][b][x]);
				ret=max(ret,max(UP[a][b][x],LO[a][b][x]));
			}
		}
		FOR(a,B) FOR(b,B) if(a!=b) FOR(c,B) FOR(d,B) if(side[a][b][c]>0 && side[a][b][d]<0) {
			if(side[c][b][d]<0) ret=max(ret,UP[a][c][b]+LO[a][d][b]-2);
		}
		return ret;
	}
}

まとめ

途中でHardに移ったのが失敗。