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