kmjp's blog

競技プログラミング参加記です

AtCoder ARC #076 : E - Connected?

未記載のARCがあったので。
https://beta.atcoder.jp/contests/arc076/tasks/arc076_c

問題

(0,0)-(R,C)の範囲の2次元座標の矩形領域で、N組の頂点対が与えられる。
各組において頂点間を線で結びたい。線は曲線でもよいが、矩形の範囲を出てはいけない。
この時、互いに交わらないように戦で結ぶことは可能か。

解法

自分も詳しくはないが、トポロジーのような感じで大まかな形を変えない範囲で図形をまげて考えてみよう。
頂点対のうち、片方でも外周部に無いものがある場合、両者を結ぶ線は接続関係を変えないまま点に縮約できるので無視してよい。

よって残るは頂点の両端が外周部にある場合である。
この場合、外周部にある頂点対において、隣接するものがあれば互いに対にして消す、ということを繰り返し全部消すことができればよい。
ABABのように頂点対の並びが互いに交差している場合はA-A間の線とB-B間の線が交わらざるを得ないため、Noが解となる。

int H,W;
int N;
int X[101010][2],Y[101010][2];
vector<pair<int,int>> V;
int edge_id(int x,int y) {
	if(x==0) return y;
	if(y==H) return H+x;
	if(x==W) return H+W+(H-y);
	if(y==0) return H+W+H+(W-x);
	return -1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H>>N;
	FOR(i,N) {
		cin>>X[i][0]>>Y[i][0]>>X[i][1]>>Y[i][1];
		
		x=edge_id(X[i][0],Y[i][0]);
		y=edge_id(X[i][1],Y[i][1]);
		if(x==-1 || y==-1) continue;
		V.push_back({x,i});
		V.push_back({y,i});
	}
	sort(ALL(V));
	vector<int> A;
	FORR(v,V) {
		if(A.size() && A.back()==v.second) A.pop_back();
		else A.push_back(v.second);
	}
	if(A.size()) return _P("NO\n");
	_P("YES\n");
	
}

まとめ

700ptなのでそこまで難しくはない。