Cod sursa(job #2709351)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 20 februarie 2021 10:48:28
Problema Robot Scor 70
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 7.66 kb
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) <<

using namespace std;

template<class T> ostream& operator<<(ostream& os, const vector<T> &v) {
  os << "["; for (auto &x : v) os << x << ", ";
  return os << "]";
}

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) const {
    auto ret = *this; ret -= other; return ret;
  }
  Point& operator+=(const Point &other) {
    x += other.x;
    y += other.y;
    return *this;
  }
  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;
  }
  friend ostream& operator<<(ostream& os, const Point &p) {
    return os << "(" << p.x << ", " << p.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(1LL * a.x * (b.y - c.y) + 1LL * b.x * (c.y - a.y) + 1LL * c.x * (a.y - b.y)); 
}

int Cross(const Point &a, const Point &b) {
  return Det(a, b, {0, 0});
}

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

vector<Point> Reorder(vector<Point> v) {
  int n = (int)v.size(); 
  int pos = 0;
  for (int i = 0; i < n; ++i) {
    if (v[i].x < v[pos].x || (v[i].x == v[pos].x && v[i].y < v[pos].y)) pos = i;
  }
  rotate(v.begin(), v.begin() + pos, v.end());
  v.emplace_back(v[0]);
  return v;
}

vector<Point> MinkowskiSum(const vector<Point> &a, const vector<Point> &b) {
  int n = (int)a.size() - 1, m = (int)b.size() - 1;
  int i = 0, j = 0;
  vector<Point> sum;
  while (i < n || j < m) {
    sum.emplace_back(a[i] + b[j]); 
    int cross = Cross(a[i + 1] - a[i], b[j + 1] - b[j]);
    if (cross >= 0) ++i;
    if (cross <= 0) ++j;
  }
  while (i < n) sum.emplace_back(a[i++] + b[0]);
  while (j < m) sum.emplace_back(a[0] + b[j++]);
  return sum;
}

pair<vector<Point>, vector<Point>> SplitUpperLower(const vector<Point> &v) {
  int n = (int)v.size();
  int pos = 0, pos2 = 0;
  for (int i = 0; i < n; ++i) {
    if (v[i].x > v[pos].x || (v[i].x == v[pos].x && v[i].y > v[pos].y)) pos = i;
    if (v[i].x < v[pos2].x || (v[i].x == v[pos2].x && v[i].y < v[pos2].y)) pos2 = i;
  }
  assert(pos2 == 0);
  vector<Point> lower(v.begin(), v.begin() + pos + 1);
  vector<Point> upper = {v[0]};
  upper.insert(upper.end(), v.rbegin(), v.rend() - pos);
//  dbg() name(upper) name(lower) endl;
  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, p.x = -p.x, p.y = -p.y;
  robot = Reorder(move(robot));

  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(sz);
    for (auto &p : obstacle) {
      cin >> p.x >> p.y; p -= start;
    }
    obstacle = Reorder(move(obstacle));
    auto sum = MinkowskiSum(obstacle, robot);
    // dbg() name(sum) endl;
    vector<Point> upper, lower; tie(upper, lower) = SplitUpperLower(sum);
    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;
}