TopCoder SRM 562 Div1 Medium CheckerFreeness

問題

平面上に黒い点がn個、白い点がm個与えられる。
これらの点は、どの3点も同一直線上にはない。


黒い点、白い点、黒い点、白い点と、色違いの点を交互に結んで出来る、
凸な四角形が一つでも存在するならば"NO"を、存在しないならば"YES"を出力せよ。

制約条件

n, m≦222

方針

条件に当てはまる凸四角形が存在する⇔黒い2点を結んだ線分と、白い2点を結んだ線分に交点が存在する。


角度の条件から、クエリだと思ってbinary indexed treeを使ってごにょごにょやる方針を立てたら、
O(n^3 log n)だけど微妙に時間が間に合わなかった。


想定解は、黒い2点を結んだ線分と、白い2点を結んだ線分に交点が存在する⇔
黒い点の凸包のどれかの辺と、白い点どれか2点の辺に交点が存在する or
白い点の凸包のどれかの辺と、黒い点どれか2点の辺に交点が存在する
という変形をする。O(n^3)の計算量(ただし定数大)。

ソースコード

inline bool intersectSS(const P &a, const P &b, const P &c, const P &d) {
  return ccw(a,b,c)*ccw(a,b,d) <= 0 &&
         ccw(c,d,a)*ccw(c,d,b) <= 0;
}

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";
	}
};

TLEする(たぶん4sくらいかかる?)やつ

int w, b;
vi wx, wy, bx, by;

void parse(vi &v, const vector<string> str){
	string s;
	rep(i, str.size()) s += str[i];
	stringstream ss(s);
	int t;
	while(ss >> t) v.pb(t);
}
inline ll op(ll x1, ll y1, ll x2, ll y2){
	return x1 * y2 - y1 * x2;
}
inline double fix(double a){
	while(a < 0) a += 2 * PI;
	while(a > 2 * PI) a -= 2 * PI;
	return a;
}

const int MX = 256;
int bit[MX];
inline void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
inline int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}

bool check(int p, int q){
	vi l, r;
	rep(i, b){
		if(op(wx[q] - wx[p], wy[q] - wy[p], bx[i] - wx[q], by[i] - wy[q]) < 0)
			l.pb(i);
		else r.pb(i);
	}

	double base = atan2(wy[q] - wy[p], wx[q] - wx[p]);
	
	vector<pair<double, double> > ls, rs;
	rep(i, l.size()){
		double a = atan2(wy[p] - by[l[i]], wx[p] - bx[l[i]]);
		double b = atan2(wy[q] - by[l[i]], wx[q] - bx[l[i]]);
		ls.pb(mp(fix(a - base), fix(b - base)));
	}
	rep(i, r.size()){
		double a = atan2(by[r[i]] - wy[p], bx[r[i]] - wx[p]);
		double b = atan2(by[r[i]] - wy[q], bx[r[i]] - wx[q]);
		rs.pb(mp(fix(a - base), fix(b - base)));
	}
	sort(all(ls));
	sort(all(rs));
	vector<double> ys;
	rep(i, rs.size()) ys.pb(rs[i].second);
	sort(all(ys));
	ys.erase(unique(all(ys)), ys.end());
	
	memset(bit, 0, sizeof(bit));
	
	for(int i = 0, j = 0; i < ls.size(); i++){
		while(j < rs.size() && rs[j].first < ls[i].first){
			int id = lower_bound(all(ys), rs[j].second) - ys.begin();
			add(id + 1, 1);
			j++;
		}
		int id = upper_bound(all(ys), ls[i].second) - ys.begin() - 1;
		if(j != sum(id + 1)){
			return 0;
		}
	}
	return 1;
}

class CheckerFreeness {
	public:
	string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY) {
		
		wx.clear(); wy.clear();
		bx.clear(); by.clear();
		
		parse(wx, whiteX); parse(wy, whiteY);
		parse(bx, blackX); parse(by, blackY);
		w = wx.size();
		b = bx.size();
		
		bool ok = 1;
		rep(j, w) rep(i, j){
			ok &= check(i, j);
			if(!ok) break;
		}
		return ok ? "YES" : "NO";
	}
};