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