2013年7月31日

UVa 10610 - Gopher and Hawks

#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

struct P {
  P (double x, double y) : x(x), y(y), len(0) {}
  bool operator==(P other) const {
    return (fabs(x - other.x) <= 1e-5) && (fabs(y - other.y) <= 1e-5);
  }
  double x, y;
  int len;
};

double dis(P a, P b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main() {
  char s[99];
  int v, m;
  while (gets(s)) {
    sscanf(s, "%d%d", &v, &m);
    if (!v && !m) {
      break;
    }
    double x, y;
    gets(s);
    sscanf(s, "%lf%lf", &x, &y);
    P start(x, y);
    gets(s);
    sscanf(s, "%lf%lf", &x, &y);
    P end(x, y);
    vector<P> all;
    while (gets(s) && s[0]) {
      sscanf(s, "%lf%lf", &x, &y);
      all.push_back(P(x, y));
    }
    all.push_back(end);
    queue<P> q;
    q.push(start);
    bool find = false;
    bool visit[9999] = {};
    while (!q.empty()) {
      P now = q.front();
      q.pop();
      if (now == end) {
        printf("Yes, visiting %d other holes.\n", now.len >= 1 ? now.len - 1 : now.len);
        find = true;
        break;
      }
      for (int i = 0; i < all.size(); i++) {
        if (!visit[i] && (dis(now, all[i]) < (m * m * 60.0 * 60.0 * v * v))) {
          all[i].len = now.len + 1;
          q.push(all[i]);
          visit[i] = true;
        }
      }
    }
    if (!find) {
      puts("No.");
    }
  }
  return 0;
}

沒有留言:

張貼留言