UVA 11853 - Paintball

题目链接

题意：就是给定一些圆，判断能否不经过这些圆从左边走到右边，如果可以要求起始和终止位置尽量往北，输出位置

思路：每次找一个超出上边界的圆dfs，如果能到下边界，就是隔断了肯定到达不了，如果隔断左右边界，就要更新答案的值

代码：

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

const int N = 1005;

int n, vis[N];

struct Circle {
	int x, y, r;
	void read() {
		scanf("%d%d%d", &x, &y, &r);
	}
} c[N];

double ans1, ans2;

bool can(Circle a, Circle b) {
	int dx = a.x - b.x;
	int dy = a.y - b.y;
	return dx * dx + dy * dy - (a.r + b.r) * (a.r + b.r) <= 0;
}

bool dfs(int u) {
	vis[u] = 1;
	if (c[u].y - c[u].r <= 0) return false;
	if (c[u].x - c[u].r <= 0) ans1 = min(ans1, c[u].y - sqrt(c[u].r * c[u].r - c[u].x * c[u].x));
	if (1000 - c[u].x - c[u].r <= 0) ans2 = min(ans2, c[u].y - sqrt(c[u].r * c[u].r - (1000 - c[u].x) * (1000 - c[u].x)));
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		if (can(c[u], c[i]))
			if (!dfs(i)) return false;
	}
	return true;
}

void solve() {
	ans1 = ans2 = 1000;
	for (int i = 0; i < n; i++) {
		if (!vis[i] && c[i].y + c[i].r >= 1000)
			if (!dfs(i)) {
				printf("IMPOSSIBLE\n");
				return;
			}
	}
	printf("0.00 %.2lf 1000.00 %.2lf\n", ans1, ans2);
}

int main() {
	while (~scanf("%d", &n)) {
		for (int i = 0; i < n; i++) {
			c[i].read();
			vis[i] = 0;
		}
		solve();
	}
	return 0;
}

UVA 11853 - Paintball(dfs）