SRM 280 DIV1 Hard DrawPlanar

SRM 枝刈り

問題 Editorial

問題

任意の平面グラフは交差しない線分だけで描けることが知られている。
平面グラフgraphが与えられる。整数座標上で交差しない線分で描くとき、それを収める(座標軸に平行な)矩形の面積を最小化せよ

  • 1 <= |graph| <= 7

解答

Editorialを見た。
基本的な方針は全探索+枝刈り。
面積を増加させながら、その面積の縦*横のどれかに収まるかを判定し、収まるならその面積が答え。
全ての連結成分が一本道の形のグラフ iff 答えが0になるので、最初に判定してやる。
全探索の中身は、単に今までの全ての辺に対して交差判定をすればいい。
以下の枝刈りを用いることができる。

  • 上下左右の反転に対して対称であるので、最初の頂点は左上の4分の1の部分のみを試せばよい
  • 次数の大きい順に試していく

また、交差判定をメモすることによって高速化することもできる。
これらなどの枝刈りや高速化をすればわりと間に合う

コメント

この問題は枝刈りといっても実際そんなに難しい考察は必要ない。
確実に枝刈りだと思えたら、怖くならずにやってみることは大事だ。
枝狩りとして「反転に対して対称なので最初は左上4分の1だけでいい」や「『潰す』ものが多いものからやっていく」というのは典型に思えるので、必ず考えよう

コード

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;  typedef vector<pair<int,int> > vpii;
typedef long long ll;   
typedef vector<string> vs; 

struct P {
	typedef int T; typedef ll T2;
	T x, y;
	P(T x_, T y_): x(x_), y(y_) {}
	P(): x(0), y(0) {}
};
inline bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; }
inline P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y); }

struct L {
	P a, b;
	L(const P &a_, const P &b_): a(a_), b(b_) {}
	const P& operator[](size_t i) const { return i ? b : a; }
};

inline int ccw(const P& a, const P& b, const P& c) {
	int ax = b.x - a.x, ay = b.y - a.y, bx = c.x - a.x, by = c.y - a.y;
	P::T2 t = (P::T2)ax*by - (P::T2)ay*bx;
	if (t > 0) return 1;
	if (t < 0) return -1;
	if((P::T2)ax*bx + (P::T2)ay*by < 0) return +2;
	if((P::T2)ax*ax + (P::T2)ay*ay < (P::T2)bx*bx + (P::T2)by*by) return -2;
	return 0;
}

const int T = 9;
char intersectmemo[T*2+1][T*2+1][T*2+1][T*2+1][T*2+1][T*2+1];
int intersectSS(const P &sa, const P &sb, const P &ta, const P &tb) {
	int a = ccw(sa,sb,ta), b = ccw(sa,sb,tb), c = ccw(ta,tb,sa), d = ccw(ta,tb,sb);
	int x = a * b, y = c * d;
	if(x == -1 && y == -1) return 0;	//cross
	else if(
		((abs(b) == 1 || b == -2) && sb == ta) ||
		((abs(b) == 1 || b ==  2) && sa == ta) ||
		((abs(a) == 1 || a == -2) && sb == tb) ||
		((abs(a) == 1 || a ==  2) && sa == tb)
		) return 2;	// point overlap
	else if(
		(x == 0 && (abs(a) + abs(b) == 1)) ||
		(y == 0 && (abs(c) + abs(d) == 1))
		) return 0;	// point overlap
	else if(x <= 0 && y <= 0) return 0;	//segment overlap
	else return 1;
}
int intersectSS_memoized(const P &sa, const P &sb, const P &ta, const P &tb) {
	int x0=sb.x-sa.x+10, y0=sb.y-sa.y+10, x1=ta.x-sa.x+10, y1=ta.y-sa.y+10, x2=tb.x-sa.x+10, y2=tb.y-sa.y+10;
	if(0<=x0&&x0<=T*2&&0<=y0&&y0<=T*2&&0<=x1&&x1<=T*2&&0<=y1&&y1<=T*2&&0<=x2&&x2<=T*2&&0<=y2&&y2<=T*2){
		char &a = intersectmemo[x0][y0][x1][y1][x2][y2];
		if(a != -1) return a;
		else return a = intersectSS(sa,sb,ta,tb);
	}
	return intersectSS(sa,sb,ta,tb);
}

vs g; int n;
bool vis[7];
int W, H;
vi ei[8], ej[8];
P ps[8];
bool o[30][30];
struct DrawPlanar {
	bool search(int i) {
		if(i == n) return true;
		rer(y, 0, H) rer(x, 0, W) if(i != 0 || (y <= (H+1)/2) && x <= (W+1)/2)
		if(!o[y][x]) {
			ps[i].x = x, ps[i].y = y;
			rep(j, i) if(g[i][j] == 'T') {
				rep(k, ei[i].size()) {
					if(intersectSS_memoized(ps[ei[i][k]], ps[ej[i][k]], ps[j], ps[i]) == 0)
						goto bad;
				}
			}
			o[y][x] = true;
			if(search(i+1)) return true;
			o[y][x] = false;
			bad:;
		}
		return false;
	}
	bool checkcycle(int i, int pare) {
		if(vis[i]) return false;
		vis[i] = true;
		bool r = true;
		rep(j, n) if(j != pare && g[i][j] == 'T')
			r &= checkcycle(j, i);
		return r;
	}
	int minArea(vector <string> graph) {
		g = graph; n = g.size();

		{
			vpii v;
			bool line = true;
			rep(i, n) {
				int deg = 0;
				rep(j, n) if(graph[i][j] == 'T') deg ++;
				line &= deg <= 2;
				v.pb(mp(-deg, i));
			}
			mset(vis, 0);
			rep(i, n) if(!vis[i]) line &= checkcycle(i, -1);
			if(line) return 0;
			sort(all(v));
			vs gg = g;
			rep(i, n) rep(j, n) g[i][j] = gg[v[i].second][v[j].second];
		}
		mset(intersectmemo, -1);

		rep(k, n) {
			ei[k].clear(), ej[k].clear();
			rep(i, k) rep(j, i) if(g[i][j] == 'T') {
				ei[k].pb(i), ej[k].pb(j);
			}
		}

		for(int area = 1; ; area ++) {
			for(W = 1; W * W <= area; W ++) if(area % W == 0) {
				H = area / W;
				if((W+1) * (H+1) < n) continue;
				mset(o, 0);
				if(search(0)) {
					return area;
				}
			}
		}
	}
};