さて不参加だったSRM562の復習。
http://community.topcoder.com/stat?c=problem_statement&pm=11565
最初にcheckerの定義があるが、簡潔に書けば「白点と黒点の集合が与えられて、白点同士を結ぶ線と、黒点同士を結ぶ線が交差するかどうか」を求める。
白点２つと黒点２つがあったとき、線が交差するかどうかは外積を使って「黒点２つが白点を結ぶ線の両側にあり、かつ白点２つが黒点を結ぶ線の両側にある」をチェックすればよい。
ただ、この方式では点を４つ選ぶのでO(N^4)かかり、N=222だと時間切れする。
よって時間の短い手法を考えなければならない。
Editorialを見ると、「２つの点に対し、各点がそこを結んだ線のどちら側にあるかをビットマップで管理する」手法が紹介されている。
これだと白点２つ黒点１つを選ぶと、残り１つの黒点をビットマップで高速に探せるので、O(N^4)ではあるのだがO(N^3)と大差ない時間で解ける。
ただ、自分が最初思いついたのはEditorialのFaster Methodだった。
それは白点と黒点の線同士が交差するなら、白点および黒点の凸包を取れば、おそらく凸包同士だけ判定すれば(内部の対角線を見なくても)どこか公差するだろうと。
実際には、黒点集合が白の凸包に含まれるかもしれないので：
- 白点の凸包に、黒点同士の線が交差する
- 黒点の凸包に、白点同士の線が交差する
の判定を行えばよい。凸包の線の数は高々O(N)なので、全部でO(N^3)で処理できる。
自分ではここまでは考えられたが、凸包をきれいに求めるアルゴリズムが時間内に書けずここで断念。
そこは蟻本に載っていたので、それを拝借してみた。
ついでに、TopCoderは入力を文字列連結→数値化するケースが多いので、そこも関数に切り出しておいた。
class CheckerFreeness { public: string concatvec(vector <string> expr) { int i; string st=""; FOR(i,expr.size()) st += expr[i]; return st; } vector<int> split_int(const string &str, char delim){ vector<int> res; size_t current = 0, found; while((found = str.find_first_of(delim, current)) != string::npos){ string s = string(str, current, found - current); res.push_back(atoi(s.c_str())); current = found + 1; } string s = string(str, current, str.size() - current); res.push_back(atoi(s.c_str())); return res; } vector< pair<int, int> > wp; vector< pair<int, int> > bp; vector<int> wi,bi; vector<int> wx,wy,bx,by; int nw,nb; int ischecker(int w1,int w2,int b1,int b2) { ll dx,dy,t1x,t1y,t2x,t2y,cr1,cr2; int i; dx = wx[w2]-wx[w1]; dy = wy[w2]-wy[w1]; t1x = bx[b1]-wx[w1]; t1y = by[b1]-wy[w1]; t2x = bx[b2]-wx[w1]; t2y = by[b2]-wy[w1]; cr1 = ((t1x*dy-t1y*dx)>0)?1:-1; cr2 = ((t2x*dy-t2y*dx)>0)?1:-1; if(cr1==cr2) return 0; dx = bx[b2]-bx[b1]; dy = by[b2]-by[b1]; t1x = wx[w1]-bx[b1]; t1y = wy[w1]-by[b1]; t2x = wx[w2]-bx[b1]; t2y = wy[w2]-by[b1]; cr1 = ((t1x*dy-t1y*dx)>0)?1:-1; cr2 = ((t2x*dy-t2y*dx)>0)?1:-1; if(cr1==cr2) return 0; return 1; } ll veccross(pair<int,int> p1,pair<int,int> p2,pair<int,int> p3) { p3.first-=p1.first;p2.first-=p1.first; p3.second-=p1.second;p2.second-=p1.second; return p3.first*(ll)p2.second-p2.first*(ll)p3.second; } vector<int> convex_hull(vector< pair<int, int> >& vp) { vector<pair<pair<int, int>, int> > sorted; vector<int> res; int i,k=0,rb; FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i)); sort(sorted.begin(),sorted.end()); res.resize(vp.size()*2); /* bottom */ FOR(i,vp.size()) { while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=0) k--; res[k++]=sorted[i].second; } /* top */ for(rb=k, i=vp.size()-2;i>=0;i--) { while(k>rb && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=0) k--; res[k++]=sorted[i].second; } res.resize(k-1); return res; } string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY) { wx = split_int(concatvec(whiteX),' '); wy = split_int(concatvec(whiteY),' '); bx = split_int(concatvec(blackX),' '); by = split_int(concatvec(blackY),' '); nw = wx.size(); nb = bx.size(); int i; wp.clear(); bp.clear(); FOR(i,wx.size()) wp.push_back(make_pair(wx[i],wy[i])); FOR(i,bx.size()) bp.push_back(make_pair(bx[i],by[i])); wi = convex_hull(wp); bi = convex_hull(bp); int w1,w2,b1,b2; FOR(w1,wi.size()) FOR(b1,nb) for(b2=b1+1;b2<nb;b2++) { if(ischecker(wi[w1],wi[(w1+1)%wi.size()],b1,b2)) return "NO"; } FOR(b1,bi.size()) FOR(w1,nw) for(w2=w1+1;w2<nw;w2++) { if(ischecker(w1,w2,bi[b1],bi[(b1+1)%bi.size()])) return "NO"; } return "YES"; } };
まとめ
凸包を使うところまでは自分で思いつけたが、凸包自体の簡潔な求めかたを知らなかった。
これで今度凸包が出たら対処できそうだ。
