POJ-3293 : Rectilinear polygon

問題概要

2次元格子点上にN(<10^5)個の点がある。これらの点を頂点とする単純で辺が軸に平行で連結で穴の無い多角形が作れるかどうか判定する。ただし、頂点は必ず垂直な辺と水平な辺にひとつずつ接続していなければならない。

解法

平面走査する。x座標を動かしながらy座標に点を追加したり、既に追加されていれば削除したりするようにする。この際に単純であるかどうかをチェックするのを忘れないこと。

acceptされたコード

#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

struct UnionFind{
	vector<int> pars;
	vector<int> ranks;

	UnionFind() {}
	UnionFind(int n) {
		init(n);
	}

	void init(int n) {
		ranks.assign(n, 0);
		pars.resize(n);
		for (int i = 0; i < n; ++i) {
			pars[i] = i;
		}
	}

	int getRoot(int x) {
		if (pars[x] == x) {
			return x;
		}
		else {
			return pars[x] = getRoot(pars[x]);
		}
	}

	void merge(int x, int y) {
		x = getRoot(x);
		y = getRoot(y);
		if ( x == y ) {
			return ;
		}

		if (ranks[x] < ranks[y]) {
			pars[x] = y;
		}
		else if (ranks[y] < ranks[x]) {
			pars[y] = x;
		}
		else {
			pars[x] = y;
			ranks[y]++;
		}
	}

	bool isSame(int x, int y) {
		return getRoot(x) == getRoot(y);
	}
};

UnionFind uf;

typedef long long int64;
const int MAX_N = int(2e5);

int N, X;
map< pair<int64,int64>, int> dict;
int64 xs[MAX_N], ys[MAX_N], nums[MAX_N];
vector<int64> ts[MAX_N];

void init() {
	scanf("%d", &N);
	dict.clear();
	for (int i = 0; i < N; ++i) {
		scanf("%lld%lld", xs+i, ys+i);
		dict[make_pair(ys[i], xs[i])] = i;
	}
	uf.init(N);
}

void compress() {
	memcpy(nums, xs, sizeof(xs));
	sort(nums, nums + N);
	X = unique(nums, nums + N) - nums;
	for (int i = 0; i < X; ++i) {
		ts[i].clear();
	}
	for (int i = 0; i < N; ++i) {
		ts[lower_bound(nums, nums + X, xs[i]) - nums].push_back(ys[i]);
	}
	for (int i = 0; i < X; ++i) {
		sort(ts[i].begin(), ts[i].end());
	}
}


int64 solve() {
	compress();

	int64 ans = 0;
	for (int i = 0; i < X; ++i) {
		if (ts[i].size()&1) {
			return -1;
		}
		for (int j = 0; j + 1 < int(ts[i].size()); ++j) {
			if (ts[i][j] == ts[i][j+1]) {
				return -1;
			}
			if (j%2 == 0) {
				uf.merge(dict[make_pair(ts[i][j], nums[i])], dict[make_pair(ts[i][j+1], nums[i])]);
				ans += ts[i][j+1] - ts[i][j];
			}
		}
	}

	set< pair<int64,int64> > eventline;
	const int64 back = nums[0] - 1;
	for (int i = 0; i < X; ++i) {
		vector< pair<int64, int64> > add;
		for (int j = 0; j < int(ts[i].size()); ++j) {
			set< pair<int64,int64> >::iterator itr = eventline.lower_bound(make_pair(ts[i][j], back));
			if (itr != eventline.end() && itr->first == ts[i][j]) {
				ans += nums[i] - itr->second;
				uf.merge(dict[*itr], dict[make_pair(ts[i][j], nums[i])]);
				eventline.erase(itr);
			}
			else {
				if ((j&1)) {
					itr = eventline.lower_bound(make_pair(ts[i][j-1], nums[X-1]+1));
					if (itr != eventline.end() && ts[i][j-1] < itr->first  && itr->first < ts[i][j]) {
						return -1;
					}
				}
				add.push_back(make_pair(ts[i][j], nums[i]));
			}
		}
		eventline.insert(add.begin(), add.end());
	}

	for (int i = 0; i + 1 < N; ++i) {
		if (!uf.isSame(i, i+1)) {
			return -1;
		}
	}

	return eventline.empty() ? ans : -1;
}

int main() {
	int T; scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		init();
		printf("%lld\n", solve());
	}
	return 0;
}