SRM 368 500pt: PolylineUnion

問題概要

線分からなる図形がいくつか与えられる。重なっているものをマージしていったとき、要素がいくつ残るか求める問題。

考えたこと

• また入力が面倒な…。
• 線分の個数とか大したことないし、やるだけ問題に思える。
• 書いた。サンプル通らない。
• 入力のパースが間違えてた。つまんない…。
• サンプル通った。投げる。
• 合わない。よく読んだら1点だけの図形とか、線分の癖に始点と終点が同じとかあるらしい。面倒くさい…。
• 馬鹿にしてんのか、って言うくらい丁寧に書いたんだけど通らない。
• union findの配列確保の数があってなかった。これだから入力面倒くさいのはいやなんだ。直したら通った。

practiceで通った解法

計算量O(線分の個数^2*線分の要素数^2)くらい。

#include <vector>
#include <string>
#include <sstream>
#include <numeric>
using namespace std;

typedef long long int64;

const int MAX_N = 100000;
int pars[MAX_N];
void init(int n){for(int i=0;i<n;i++)pars[i]=i;}
int getRoot(int x){return x==pars[x]?x:(pars[x]=getRoot(pars[x]));}
bool isSame(int x, int y){return getRoot(x)==getRoot(y);}
void merge(int x, int y){pars[getRoot(x)]=getRoot(y);}

struct PolylineUnion {

	int countComponents(vector <string> polylines) {

		//データの読み取り
		//string str = accumulate(polylines.begin(), polylines.end(), string());
		string str = "";
		for(int i=0; i<(int)polylines.size(); i++){
			str += polylines[i];
		}
		stringstream sss(str);
		polylines.clear();
		while(sss >> str){
			polylines.push_back(str);
		}
		const int N = polylines.size();
		vector< vector< pair<int,int> > >lines(N);
		for(int i=0; i<N; i++){
			for(int j=0; j<(int)polylines[i].length(); j++){
				if(polylines[i][j] == '-' || polylines[i][j] == ','){
					polylines[i][j] = ' ';
				}
			}
			stringstream ss(polylines[i]);
			int x, y;
			while(ss >> x >> y){
				lines[i].push_back( make_pair(x,y) );
			}
		}

		//union find
		init(N);
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				if(cross(lines[i], lines[j])){
					merge(i,j);
				}
			}
		}

		//構成成分を数える
		int ret = 0;
		for(int i=0; i<N; i++)if(getRoot(i) == i){
			ret++;
		}

		return ret;
	}

	bool cross(const vector< pair<int,int> >& as, const vector< pair<int,int> >& bs){
		for(int i=0; i<(int)as.size()-1; i++){
			for(int j=0; j<(int)bs.size()-1; j++){
				if(sub_cross(as[i], as[i+1], bs[j], bs[j+1])){
					return true;
				}
			}
		}
		for(int i=0; i<(int)as.size(); i++){
			for(int j=0; j<(int)bs.size()-1; j++){
				if(is_on(bs[j], bs[j+1], as[i])){
					return true;
				}
			}
		}
		for(int i=0; i<(int)as.size()-1; i++){
			for(int j=0; j<(int)bs.size(); j++){
				if(is_on(as[i], as[i+1], bs[j])){
					return true;
				}
			}
		}
		for(int i=0; i<(int)as.size(); i++){
			for(int j=0; j<(int)bs.size(); j++){
				if(as[i] == bs[j]){
					return true;
				}
			}
		}
		return false;
	}

	bool sub_cross(const pair<int,int> a1, const pair<int,int> a2, const pair<int,int> b1, const pair<int,int> b2){
		return det(a1,a2,b1)*det(a1,a2,b2)<0 && det(b1,b2,a1)*det(b1,b2,a2)<0;
	}

	bool is_on(const  pair<int,int> p, const pair<int,int> q, const pair<int,int>a){
		int minx = min(p.first, q.first);
		int maxx = max(p.first, q.first);
		int miny = min(p.second, q.second);
		int maxy = max(p.second, q.second);
		int x = a.first, y = a.second;
		if(minx <= x && x <= maxx && miny <= y && y <= maxy && det(p,q,a)==0){
			return true;
		}
		return false;
	}

	int64 oprod(const pair<int,int> a, const pair<int,int> b){
		return (int64)a.first*b.second - (int64)a.second*b.first;
	}

	int det(const pair<int,int> a, const pair<int,int> b, const pair<int,int> c){
		return sign(oprod(a,b) + oprod(b,c) + oprod(c,a));
	}

	int sign(int64 x){
		return x>0?1:x==0?0:-1;
	}
};