POJ 2296 Map Labeler

题目链接

题意：

坐标轴上有N个点，要在每个点上贴一个正方形，这个正方形的横竖边分别和x，y轴平行，并且要使得点要么在正方形的上面那条边的中点，或者在下面那条边的中点，并且任意两个点的正方形都不重叠（可以重边）。问正方形最大边长可以多少？

思路：显然的2-sat问题，注意判断两个矩形相交的地方，细节

代码：

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

const int MAXNODE = 205;

struct TwoSet {
	int n;
	vector<int> g[MAXNODE * 2];
	bool mark[MAXNODE * 2];
	int S[MAXNODE * 2], sn;

	void init(int tot) {
		n = tot * 2;
		for (int i = 0; i < n; i += 2) {
			g[i].clear();
			g[i^1].clear();
		}
		memset(mark, false, sizeof(mark));
	}

	void add_Edge(int u, int uval, int v, int vval) {
		u = u * 2 + uval;
		v = v * 2 + vval;
		g[u^1].push_back(v);
		g[v^1].push_back(u);
	}

	void delete_Edge(int u, int uval, int v, int vval) {
		u = u * 2 + uval;
		v = v * 2 + vval;
		g[u^1].pop_back();
		g[v^1].pop_back();
	}

	bool dfs(int u) {
		if (mark[u^1]) return false;
		if (mark[u]) return true;
		mark[u] = true;
		S[sn++] = u;
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if (!dfs(v)) return false;
		}
		return true;
	}

	bool solve() {
		for (int i = 0; i < n; i += 2) {
			if (!mark[i] && !mark[i + 1]) {
				sn = 0;
				if (!dfs(i)){
					for (int j = 0; j < sn; j++)
						mark[S[j]] = false;
					sn = 0;
					if (!dfs(i + 1)) return false;
				}
			}
		}
		return true;
	}
} gao;

const int N = 105;

int t, n;
struct Point {
	int x, y;
	void read() {
		scanf("%d%d", &x, &y);
		x *= 2;
	}
} p[N];

bool judge(int len) {
	gao.init(n);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (p[i].x + len <= p[j].x - len || p[j].x + len <= p[i].x - len) continue;
			for (int x = 0; x < 2; x++) {
				for (int y = 0; y < 2; y++) {
					int y1, y2, y3, y4;
					if (x == 0) {
						y1 = p[i].y - len;
						y2 = p[i].y;
					} else {
						y1 = p[i].y;
						y2 = p[i].y + len;
					}
					if (y == 0) {
						y3 = p[j].y - len;
						y4 = p[j].y;
					} else {
						y3 = p[j].y;
						y4 = p[j].y + len;
					}
					if ((y1 >= y3 && y1 < y4) 
							|| (y2 > y3 && y2 <= y4)
							|| (y3 >= y1 && y3 < y2)
							|| (y3 > y2 && y4 <= y2))
						gao.add_Edge(i, x, j, y);
				}
			}
		}
	}
	return gao.solve();
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			p[i].read();
			int l = 0, r = 20000;
			while (l < r) {
				int mid = (l + r) / 2;
				if (judge(mid)) l = mid + 1;
				else r = mid;
			}
			printf("%d\n", l - 1);
	}
	return 0;
}