HDU 3622 Bomb Game(2-sat)

HDU 3622 Bomb Game

题目链接

题意：求一个最大半径，使得每个二元组的点任选一个，可以得到所有圆两两不相交

思路：显然的二分半径，然后2-sat去判定即可

代码：

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

const int MAXNODE = 105;

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 n;

struct Point {
	double x, y;
	void read() {
		scanf("%lf%lf", &x, &y);
	}
} p[N][2];

inline double dis(Point a, Point b) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

inline bool xj(Point a, Point b, double r) {
	if (dis(a, b) > 2 * r) return false;
	return true;
}

bool judge(double r) {
	gao.init(n);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int x = 0; x < 2; x++) {
				for (int y = 0; y < 2; y++) {
					if (xj(p[i][x], p[j][y], r))
						gao.add_Edge(i, x, j , y);
				}
			}
		}
	}
	return gao.solve();
}

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