TopCode SRM 368 Div1 Medium PolylineUnion

問題

折れ線とは、線分の連なりであり、それぞれの線分の始点が前の線分の終点に一致しているものをいう。
折れ線がいくつか与えられる。

折れ線同士が共有点を持つとき、それらの線分は一つの絵になっていると言う。
与えられた折れ線の集合は、いくつの絵になっているか、求めよ。

制約条件

0≦点の座標≦10000
点は文字列によって与えられ、それの長さは合計2500文字以下
折れ線がただ一つの点からなる場合もある

方針

線分同士の交わりを全てチェックし、線分同士が交わるとき、
Union-Findで交わった折れ線をマージする。

線分が一点のみからなる場合は、
spaghetti sourceの線分交差判定では判定できないので、
ccwを使って自分で確認する。

ソースコード

線分交差判定はspaghetti sourceのなので略。

int p[3000];
int root(int x){
  return x==p[x]?x:root(p[x]);
}
void merge(int a,int b){
  a=root(a); b=root(b);
  if(a!=b)p[a]=b;
}
class PolylineUnion {
  public:
  int countComponents(vector <string> polylines) {
    string s=accumulate(all(polylines),string());
    stringstream ss(s);
    vector<vector<P> > pt;
    rep(i,3000)p[i]=i;
    
    while(ss>>s){
      rep(i,s.size())if(s[i]==','||s[i]=='-')s[i]=' ';
      stringstream tt(s);
      int x,y;
      vector<P> v;
      while(tt>>x>>y)v.pb(P(x,y));
      if(v.size()==1)v.pb(v[0]);
      pt.pb(v);
    }
    
    rep(i,pt.size())rep(j,pt[i].size()-1)rep(k,i)rep(l,pt[k].size()-1)
    if(intersectSS(L(pt[i][j],pt[i][j+1]),L(pt[k][l],pt[k][l+1]))||
      ccw(pt[i][j],pt[k][l],pt[i][j+1])==-2||
      ccw(pt[k][l],pt[i][j],pt[k][l+1])==-2)merge(i,k);
    
    set<int> t;
    rep(i,pt.size())t.insert(root(i));
    return (int)t.size();
  }