UVA 11853 - Paintball(dfs）

UVA 11853 - Paintball

題目鏈接

題意：就是給定一些圓，判斷能否不經過這些圓從左邊走到右邊，如果可以要求起始和終止位置盡量往北，輸出位置

思路：每次找一個超出上邊界的圓dfs，如果能到下邊界，就是隔斷了肯定到達不了，如果隔斷左右邊界，就要更新答案的值

代碼：

#include 
#include 
#include 
#include 
#include 
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;
}