SRM 368 Div1 Medium PolylineUnion

問題

折れ線グラフが以下の形式で1つ以上与えられる。互いに交差している折れ線グラフを1つの集合と数えると、いくつの集合になるか。

1つの折れ線は1つ以上の線分からなり、点同士は'-'で区切られ、点は','で区切られる2つの非負整数で表現される。' 'で区切られているものは別の折れ線に属する。

やりかた

与えられる書式を処理しやすいように整形するのが面倒。折れ線グラフもすべて1つの線分に分解してしまったのち、各線分同士の交差をすべて調べてUnion-Findしていくつのグループになるか調べるのが手っ取り早い。

以下きたないソース。

//Union-Findのソースは略

struct seg{
  int x1, y1, x2, y2;
};

class PolylineUnion {  
public:
  int N;
  vector<seg> poly;
  void dec(string s){
    stringstream ss(s);
    string t;
    while(ss >> t){
      for(int i = 0; i < t.length(); i++) if(t[i] == '-') t[i] = ' ';
      stringstream sss(t);
      vector<string> piece;
      string x; 
      while(sss >> x)
	piece.push_back(x);
      
      if(piece.size() == 1){
	for(int j = 0; j < (int)piece[0].size(); j++) 
	  if(piece[0][j] == ',') piece[0][j] = ' ';
	stringstream s1(piece[0]);
	seg p1;
	s1 >> p1.x1 >> p1.y1; p1.x2 = p1.x1, p1.y2 = p1.y1;
	poly.push_back(p1);
      }else{
	for(int i = 0; i < (int)piece.size() - 1; i++){
	  for(int j = 0; j < (int)piece[i].size(); j++) 
	    if(piece[i][j] == ',') piece[i][j] = ' ';
	  for(int j = 0; j < (int)piece[i + 1].size(); j++) 
	    if(piece[i + 1][j] == ',') piece[i + 1][j] = ' ';
	
	  stringstream s1(piece[i]), s2(piece[i + 1]);
	  seg p1;
	  s1 >> p1.x1 >> p1.y1; s2 >> p1.x2 >> p1.y2;
	  poly.push_back(p1);
	}
      }
    }
  }

  int crs(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
    return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3);
  }
	
  bool intersects(seg a, seg b) {
    ll x1 = a.x1, y1 = a.y1, x2 = a.x2, y2 = a.y2;
    ll x3 = b.x1, y3 = b.y1, x4 = b.x2, y4 = b.y2;
    int c1 = crs(x1, y1, x2, y2, x3, y3);
    int c2 = crs(x1, y1, x2, y2, x4, y4);
    int c3 = crs(x3, y3, x4, y4, x1, y1);
    int c4 = crs(x3, y3, x4, y4, x2, y2);
    if(c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0)
      return (min(x3, x4) <= x1 && x1 <= max(x3, x4) && min(y3, y4) <= y1 && y1 <= max(y3, y4)) ||
	(min(x3, x4) <= x2 && x2 <= max(x3, x4) && min(y3, y4) <= y2 && y2 <= max(y3, y4)) ||
	(min(x1, x2) <= x3 && x3 <= max(x1, x2) && min(y1, y2) <= y3 && y3 <= max(y1, y2)) ||
	(min(x1, x2) <= x4 && x4 <= max(x1, x2) && min(y1, y2) <= y4 && y4 <= max(y1, y2));
    return min(c1, c2) <= 0 && 0 <= max(c1, c2) && min(c3, c4) <= 0 && 0 <= max(c3, c4);
  }

  int countComponents(vector <string> polylines) {
    poly.clear();
    string s = accumulate(ALL(polylines), string());
    dec(s);
    N = poly.size();
    uf_init(N);
    for(int i = 0; i < N; i++)
      for(int j = i + 1; j < N; j++)
	if(intersects(poly[i], poly[j])) uf_unite(i, j); //交差するものは同じグループに
	

    set<int> sect;
    for(int i = 0; i < N; i++) sect.insert(uf_find(i)); //いくつのグループになったか
    return (int)sect.size();
  }