TopCoder SRM 562 Div1 Medium CheckerFreeness

問題

座標平面上に白い点がn個、黒い点がm個与えられる。
これらの点から異なる4点を選び、checkerな四角形を作ることができるならば、NOを、
作ることができないならばYESを答えよ。

ただし、checkerな四角形とは、白い点、黒い点、白い点、黒い点を順に結んでできる、凸四角形のことを言う。

制約条件

n, m≦222
1≦座標≦10^7

方針

白い点二つを結んでできる線分と、黒い点二つを結んでできる線分が交差するならば、
それらの点を使ってchekerな四角形を作ることができる。

このとき、白い点の凸包と黒い点のクリーク辺が交わるか、
黒い点の凸包と、白い点のクリーク辺が交わるかのどちらか。

ソースコード

vi parse(vector<string> &v){
	string s;
	vi res;
	int t;
	
	rep(i, v.size()) s += v[i];
	stringstream ss(s);
	while(ss >> t) res.pb(t);
	return res;
}

bool check(G &h, G &ps){
	G g = convex_hull(h);
	rep(i, ps.size()) rep(j, i) rep(k, g.size()){
		if(intersectSS(ps[i], ps[j], g[k], g[(k + 1) % g.size()])) return 1;
	}
	return 0;
}

class CheckerFreeness {
	public:
	string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY) {
		
		vi wx = parse(whiteX), wy = parse(whiteY);
		vi bx = parse(blackX), by = parse(blackY);
		
		G w, b;
		rep(i, wx.size()) w.pb(P(wx[i], wy[i]));
		rep(i, bx.size()) b.pb(P(bx[i], by[i]));
		
		return check(w, b) || check(b, w) ? "NO" : "YES";
	}
};