Cod sursa(job #2707168)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 16 februarie 2021 16:43:53
Problema Robot Scor 25
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 6.67 kb
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int INF = (int)1e9 + 10;

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 Det(const Point &a, const Point &b, const Point &c) {
  return 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;
}

// pfoai ca intersectia asta segment-poligon nu i numa segment segment
// de fapt ca pot fi si puncte fix de pe poligon...
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 3;
  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) {
    int total = 0;
    for (int obs = 0; obs < (int)upper_hulls.size(); ++obs) {
      //bool found_x = false, found_y = false;
      auto &upper = upper_hulls[obs];
      for (int i = 0; i + 1 < (int)upper.size(); ++i) {
        /*
        found_x |= upper[i] == nodes[x];
        found_x |= upper[i + 1] == nodes[x];
        found_y |= upper[i] == nodes[y];
        found_y |= upper[i + 1] == nodes[y];
        */

        if (nodes[x] == upper[i] && nodes[y] == upper[i + 1]) 
          return true;
        if (nodes[y] == upper[i] && nodes[x] == upper[i + 1])
          return true;
        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) {
        /*
        found_x |= lower[i] == nodes[x];
        found_x |= lower[i + 1] == nodes[x];
        found_y |= lower[i] == nodes[y];
        found_y |= lower[i + 1] == nodes[y];
        */

        if (nodes[x] == lower[i] && nodes[y] == lower[i + 1])
          return true;
        if (nodes[y] == lower[i] && nodes[x] == lower[i + 1])
          return true;
        total += SegmInters(nodes[x], nodes[y], lower[i], lower[i + 1]);
      }
    }

    return total <= 2;
  };
  
  int n = (int)nodes.size();
  vector<vector<double>> cost(n, vector<double>(n, 1e9));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) if (i != j) {
      if (IsSafe(i, j)) {
        // dbg() name(i) name(j) endl;
        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, 1e9);

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

  /*
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      dbg() cost[i][j] << ' ';
    }
    dbg() endl;
  }
  */
  
  while (!pq.empty()) {
    double d; int node; tie(d, node) = pq.top(); pq.pop();
    if (d != dist[node]) continue;
    if (node == finish) return d;
    // dbg() name(node) name(d) endl;

    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);
        // dbg() name(i) name(dist[i]) endl;
      }
    }
  }
  return dist[finish];
}

int main() {
#ifndef LOCAL_DEFINE
  ifstream cin("robot.in");
  ofstream cout("robot.out");
#endif

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

//  for (int i = 0; i < (int)nodes.size(); ++i) { 
//    dbg() name(i) name(nodes[i].x) name(nodes[i].y) endl;
//  }

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