Cod sursa(job #2707231)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 16 februarie 2021 18:07:34
Problema Robot Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.72 kb
#include <bits/stdc++.h>

using namespace std;

const int INF = (int)1e9 + 10;
const double EPS = 1e-4;

struct Point {
  int x, y;
  Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
  Point operator-(const Point &other) const {
    auto ret = *this; ret -= other; return ret;
  }
  Point& operator-=(const Point &other) {
    x -= other.x;
    y -= other.y;
    return *this;
  }
  bool operator<(const Point &other) const {
    if (x != other.x) return x < other.x;
    return y < other.y;
  }
  bool operator==(const Point &other) const {
    return x == other.x && y == other.y;
  }
};

double Dist(const Point &a, const Point &b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int Sgn(int x) {
  return x < 0 ? -1 : x == 0 ? 0 : 1;
}

int Det(const Point &a, const Point &b, const Point &c) {
  return Sgn(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)); 
}

pair<vector<Point>, vector<Point>> GetHulls(vector<Point> pts) {
  int n = (int)pts.size();
  sort(pts.begin(), pts.end());

  vector<Point> upper, lower;
  for (int i = 0; i < n; ++i) {
    while ((int)upper.size() >= 2 && 
      Det(upper.rbegin()[1], upper.rbegin()[0], pts[i]) >= 0) {
      upper.pop_back();
    }
    upper.emplace_back(pts[i]);

    while ((int)lower.size() >= 2 &&
      Det(lower.rbegin()[1], lower.rbegin()[0], pts[i]) <= 0) {
      lower.pop_back();
    }
    lower.emplace_back(pts[i]);
  }

  return {upper, lower};
}

bool InsidePoly(
  const vector<Point> &upper,
  const vector<Point> &lower, 
  const Point &p) {

  if (p.x <= upper[0].x || upper.back().x <= p.x) return false;

  int u = upper_bound(upper.begin(), upper.end(), p) - upper.begin();
  int l = upper_bound(lower.begin(), lower.end(), p) - lower.begin();
  return Det(upper[u - 1], upper[u], p) < 0 &&
         Det(lower[l - 1], lower[l], p) > 0; 
}

vector<Point> GetNodes(
  const vector<vector<Point>> &upper_hulls,
  const vector<vector<Point>> &lower_hulls) {

  int m = (int)upper_hulls.size();

  auto InsideAny = [&](const Point &p) {
    for (int i = 0; i < m; ++i) {
      if (InsidePoly(upper_hulls[i], lower_hulls[i], p)) return true;
    }
    return false;
  };
  
  vector<Point> nodes;
  for (int i = 0; i < m; ++i) {
    for (auto &p : upper_hulls[i]) {
      if (!InsideAny(p)) nodes.emplace_back(p);
    }
    for (auto &p : lower_hulls[i]) {
      if (!InsideAny(p)) nodes.emplace_back(p);
    }
  }
  sort(nodes.begin(), nodes.end());
  nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
  return nodes;
}

bool Distinct(const Point &a, const Point &b, const Point &p, const Point &q) {
  return !(a == p || a == q) && !(b == p || b == q);  
}

int SegmInters(const Point &a, const Point &b, const Point &p, const Point &q) {
  if (Det(a, b, p) * Det(a, b, q) < 0 && 
      Det(p, q, a) * Det(p, q, b) < 0) return 4;
  if (Distinct(a, b, p, q))
    return 2 * (Det(a, b, p) * Det(a, b, q) <= 0 && 
                Det(p, q, a) * Det(p, q, b) <= 0);
  return Det(a, b, p) * Det(a, b, q) <= 0 && 
         Det(p, q, a) * Det(p, q, b) <= 0;
}

vector<vector<double>> GetCosts(
  const vector<vector<Point>> &upper_hulls,
  const vector<vector<Point>> &lower_hulls,
  const vector<Point> &nodes) {

  auto IsSafe = [&](int x, int y) {
    for (int obs = 0; obs < (int)upper_hulls.size(); ++obs) {
      int total = 0;
      auto &upper = upper_hulls[obs];
      for (int i = 0; i + 1 < (int)upper.size(); ++i) {
        total += SegmInters(nodes[x], nodes[y], upper[i], upper[i + 1]);
      }
      auto &lower = lower_hulls[obs]; 
      for (int i = 0; i + 1 < (int)lower.size(); ++i) {
        total += SegmInters(nodes[x], nodes[y], lower[i], lower[i + 1]);
      }
      if (total > 3) return false;
    }

    return true;
  };
  
  int n = (int)nodes.size();
  vector<vector<double>> cost(n, vector<double>(n, 1e18));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) if (i != j) {
      if (IsSafe(i, j)) {
        cost[i][j] = Dist(nodes[i], nodes[j]);
      }
    }
  }
  return cost;
}

double Dijkstra(const vector<vector<double>> &cost, int start, int finish) {
  using State = pair<double, int>;
  priority_queue<State, vector<State>, greater<State>> pq;

  int n = (int)cost.size();
  vector<double> dist(n, 1e18);

  pq.emplace(0, start);
  dist[start] = 0;

  while (!pq.empty()) {
    double d; int node; tie(d, node) = pq.top(); pq.pop();
    if (fabs(d - dist[node]) > EPS) continue;
    if (node == finish) return d;

    for (int i = 0; i < n; ++i) {
      if (cost[node][i] + d < dist[i]) {
        dist[i] = cost[node][i] + d;
        pq.emplace(dist[i], i);
      }
    }
  }
  return dist[finish];
}

int main() {
  ifstream cin("robot.in");
  ofstream cout("robot.out");

  int n; cin >> n;
  vector<Point> robot(n);
  Point start(INF, INF);
  for (auto &p : robot) {
    cin >> p.x >> p.y;
    start.x = min(start.x, p.x);
    start.y = min(start.y, p.y);
  }
  for (auto &p : robot) p -= start;
  int m; cin >> m;
  vector<vector<Point>> upper_hulls(m), lower_hulls(m); 
  for (int obs = 0; obs < m; ++obs) {
    int sz; cin >> sz;
    vector<Point> obstacle; obstacle.reserve(n * sz);
    for (int i = 0; i < sz; ++i) {
      Point p; cin >> p.x >> p.y; p -= start;
      for (auto &q : robot) {
        obstacle.emplace_back(p - q);
      }
    }
    vector<Point> upper, lower; tie(upper, lower) = GetHulls(move(obstacle));
    upper_hulls[obs] = move(upper);
    lower_hulls[obs] = move(lower);
  }
  Point finish; cin >> finish.x >> finish.y; finish -= start;
   
  auto nodes = GetNodes(upper_hulls, lower_hulls);
  nodes.emplace_back(0, 0);
  nodes.emplace_back(finish);
  auto cost = GetCosts(upper_hulls, lower_hulls, nodes);

  auto ans = Dijkstra(cost, cost.size() - 2, cost.size() - 1);
  if (ans > 1e17) cout << "-1\n";
  else cout << fixed << setprecision(2) << ans << endl;
}