Cod sursa(job #1220701)

Utilizator vlad_DVlad Dumitriu vlad_D Data 18 august 2014 09:38:08
Problema Robot Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.32 kb
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> point;
typedef vector<point> poly;
#define pb push_back
#define mp make_pair
#define x first
#define y second

inline void read_poly(poly& p) {
  int n;
  scanf("%d", &n);
  p.resize(n);
  for (int i = 0; i < n; ++i) scanf("%d %d", &p[i].x, &p[i].y);
}

poly robot;
point r;
vector<poly> obst;

inline int cross(point a, point b, point c) {
  int ax = a.x - b.x;
  int ay = a.y - b.y;
  int bx = c.x - b.x;
  int by = c.y - b.y;
  return ax * by - ay * bx;
}
inline int dist2(point a, point b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
void enlarge(poly& p, point origin) {
  int n = p.size();
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < robot.size(); ++j)
      p.pb(mp(p[i].x + origin.x - robot[j].x, p[i].y + origin.y - robot[j].y));
  // The new polygon is the convex hull.
  sort(p.begin(), p.end());
  unique(p.begin(), p.end());
  n = p.size();
  poly h;
  vector<int> used(n, 0);
  int lp = 0;
  for (int i = 0; i < n; ++i) if (p[i].x < p[lp].x) lp = i;
  int start = lp;
  h.pb(p[start]);
  while (1) {
    int now = -1;
    int dist = 0;
    for (int i = 0; i < n; ++i) {
      if (i == lp || used[i]) continue;
      if (now == -1) now = i;
      int c = cross(p[i], p[lp], p[now]);
      int d = dist2(p[i], p[lp]);
      if (c < 0) { now = i; dist = d; }
      else if (c == 0 && d > dist) { now = i; dist = d; }
    }
    if (now == -1) break;
    lp = now;
    used[lp] = 1;
    if (lp == start) break;
    h.pb(p[lp]);
  }
  p = h;
}

inline int collinear(point a, point b, point c) {
  return cross(a, b, c) == 0;
}

inline int get_area(const poly& p) {
  int area = 0;
  for (int i = 0; i + 1 < p.size(); ++i) area += p[i].x * p[i+1].y - p[i+1].x * p[i].y;
  return (area < 0) ? -area : area;
}

inline int get_area(point a, const poly& p) {
  int area = 0;
  for (int i = 0; i + 1 < p.size(); ++i) {
    vector<point> p2;
    p2.pb(p[i]); p2.pb(p[i+1]); p2.pb(a); p2.pb(p[i]);
    area += get_area(p2);
  }
  return area;
}

inline int inside(point a, const poly& p) {
  return (get_area(p) == get_area(a, p)); 
}

inline int on_side(point a, const poly& p) {
  for (int i = 0; i + 1 < p.size(); ++i)
    if (collinear(a, p[i], p[i+1]) && a >= min(p[i], p[i+1]) && a <= max(p[i], p[i+1])) return 1;
  return 0;
}

void get_intersection(point a, point b, point c, point d, set<pair<double, double> >& sp) {
  double A1, B1, C1, A2, B2, C2;
  A1 = a.y - b.y;
  B1 = b.x - a.x;
  C1 = A1 * a.x + B1 * a.y;
  A2 = c.y - d.y;
  B2 = d.x - c.x;
  C2 = A2 * c.x + B2 * c.y;

  double det = A1 * B2 - B1 * A2; 
  double err = 1e-09;
  if (fabs(det) <= err) return;
  pair<double, double> i = mp((B2 * C1 - B1 * C2) / det, (A1 * C2 - A2 * C1) / det);
  if (i.x >= -err + min(a.x, b.x) && i.x <= err + max(a.x, b.x))
  if (i.x >= -err + min(c.x, d.x) && i.x <= err + max(c.x, d.x))
  if (i.y >= -err + min(a.y, b.y) && i.y <= err + max(a.y, b.y))
  if (i.y >= -err + min(c.y, d.y) && i.y <= err + max(c.y, d.y)) {
    sp.insert(i);
  }
}

// If line [a, b] goes through p.
int intersect(point a, point b, const poly& p) {
  // If [a, b] is on the same line as one side of p, return 0.
  for (int i = 0; i + 1 < p.size(); ++i) 
    if (collinear(a, p[i], p[i+1]) && collinear(b, p[i], p[i+1])) return 0;
  int s1 = on_side(a, p), s2 = on_side(b, p);
  // Both points on some side, return 1.
  if (s1 && s2) return 1;
  // At least one point inside, return 1.
  if (!s1 && inside(a, p)) return 1;
  if (!s2 && inside(b, p)) return 1;
  // Get all intersection points, there should be at most one.
  set<pair<double, double> > sp;
  for (int i = 0; i + 1 < p.size(); ++i) get_intersection(a, b, p[i], p[i+1], sp);
  return sp.size() > 1;
}
double get_dist(point a, point b) {
  if (a == b) return 0;
  for (int i = 0; i < obst.size(); ++i) if (intersect(a, b, obst[i])) return 1e9;
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); 
}

vector<point> v;
double C[1024][1024];
int main() {
  // Read input.
  freopen("robot.in", "r", stdin);
  freopen("robot.out", "w", stdout);
  read_poly(robot);
  int m;
  scanf("%d", &m);
  obst.resize(m);
  for (int i = 0; i < m; ++i) {
    read_poly(obst[i]);
  }
  int fx, fy;
  scanf("%d %d", &fx, &fy);

  // Transform robot to one point by enlarging the obstacles.
  r = robot[0];
  for (int i = 0; i < robot.size(); ++i) r = min(r, robot[i]);
  for (int i = 0; i < obst.size(); ++i) enlarge(obst[i], r);
  int miny = r.y;
  for (int i = 0; i < robot.size(); ++i) miny = min(miny, robot[i].y); 
  fy += r.y - miny;

  // Generate points that can be visited and the distance between them.
  vector<point> v;
  v.pb(r);
  v.pb(mp(fx, fy));
  for (int i = 0; i < obst.size(); ++i) {
    for (int j = 0; j < obst[i].size(); ++j) v.pb(obst[i][j]);
    obst[i].pb(obst[i][0]);
  }
  for (int i = 0; i < v.size(); ++i)
    for (int j = 0; j <= i; ++j) C[i][j] = C[j][i] = get_dist(v[i], v[j]);
  
  // Min distance from 0 to 1.
  vector<double> dist(v.size(), 1e9);
  vector<int> done(v.size(), 0);
  dist[0] = 0.0;
  while (!done[1]) {
    double min_d = 1e9;
    int poz = -1;
    for (int i = 0; i < v.size(); ++i) if (!done[i] && dist[i] < min_d) { poz = i; min_d = dist[i]; } 
    done[poz] = 1;
    for (int i = 0; i < v.size(); ++i) dist[i] = min(dist[i], min_d + C[poz][i]);
  }
  printf("%lf\n", dist[1]);
  return 0;
}