TopCoder SRM 332 Div1 Medium RestoringPolygon

問題

y軸に平行な線分がいくつか与えられる。
これらのうち、好きなものと、任意のx軸に平行な線分を使って、辺が全て座標軸に平行で、
自己交差のない単純多角形を描きたい。

描ける多角形のうち、もっとも辺の多いものの辺の数はいくつか、求めよ。

制約条件

線分の個数≦16

方針

使う線分を2^n通り試す。

使う線分の集合を決めると、
x座標ごとに区切って見たときに、同じx座標の点は、
y座標が小さい順に2個ずつ線分で結ばれることになる。

すなわち、描かれる多角形の候補が一意に定まる。
あとはこの候補がvalidであるか（自己交差があったりしないか）をチェックすればいい。

y座標の順にソートするのを忘れててはまった。

ソースコード

struct cmp{
	double x;
	cmp(double x) : x(x){}
	bool operator()(const L &s, const L &t){
		bool fs = abs(s[0].real() - x) < EPS || abs(s[1].real() - x) < EPS;
		bool ft = abs(t[0].real() - x) < EPS || abs(t[1].real() - x) < EPS;
		if(fs != ft) return fs;
		const P a = abs(s[0].real() - x) < EPS ? s[0] : s[1];
		const P b = abs(t[0].real() - x) < EPS ? t[0] : t[1];
		return a.imag() < b.imag();
	}
};

bool ok(const vector<L> ls){
	int n = ls.size();
	bool use[50] = {};
	
	vector<P> ps;
	ps.pb(ls[0][0]); ps.pb(ls[0][1]);
	use[0] = 1;
	
	rep(k, n - 1){
		bool ok = 0;
		rep(i, n) if(!use[i]) rep(j, 2) if(abs(ps.back() - ls[i][j]) < EPS){
			ps.pb(ls[i][1 - j]);
			use[i] = 1;
			ok = 1;
			goto NEXT;
		}
		NEXT:
		if(!ok) return 0;
	}
	if(abs(ps.back() - ps[0]) > EPS) return 0;
	ps.pop_back();
	
	rep(i, n) rep(j, i - 2){
		if(i == n - 1 && j == 0) continue;
		if(intersectSS(L(ps[i], ps[(i + 1) % n]), L(ps[j], ps[j + 1])))
			return 0;
	}
	
	return 1;
}

class RestoringPolygon {
	public:
	int restore(vector <int> x1, vector <int> x2, vector <int> y) 
	{
		int n = y.size();
		int ans = 0;
		
		rep(i, 1 << n) if(i){
			vector<L> ls, tate;
			set<int> xs;
			rep(j, n) if(i & 1 << j){
				ls.pb(L(P(x1[j], y[j]), P(x2[j], y[j])));
				xs.insert(x1[j]);
				xs.insert(x2[j]);
			}
			each(j, xs){
				sort(all(ls), cmp(*j));
				
				int pp = -1, k = 0;
				
				for(; k < ls.size(); k++){
					int p = 0;
					for(; p < 2 && abs(ls[k][p].real() - *j) > EPS; p++);
					if(p >= 2) break;
					
					if(k % 2 == 1) tate.pb(L(ls[k - 1][pp], ls[k][p]));
					pp = p;
				}
				
				if(k % 2) goto FAIL;
			}
			ls.insert(ls.end(), all(tate));
			if(ok(ls)) ans = max(ans, (int)ls.size());
			
			FAIL:;
		}
		return ans;
	}
};