Cod sursa(job #1247087)

Utilizator dariusdariusMarian Darius dariusdarius Data 22 octombrie 2014 03:11:43
Problema Robot Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.66 kb
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 12;
const int MAX_M = 27;
const int MAX_POINTS = 3000;
const double INFINITE = 1.e9;
const double EPSILON = 1.e-3;

struct Point {
    double x, y;
    Point() {}
    Point(double xx, double yy) {
        x = xx; y = yy;
    }
    inline bool operator < (const Point &other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
} points[MAX_POINTS];
pair<int, int> position[MAX_POINTS];
double dist[MAX_POINTS];
int m;


inline bool cmp(const pair<int, double> &a, const pair<int, double> &b) {
    return a.second > b.second;
}

inline double get_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));
}

inline double cross_product(const Point &a, const Point &b, const Point &c) {
    return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}

struct Polygon {
    vector<Point> v;
    Polygon() {}
    Polygon(int n) {v.assign(n, Point());}
    Polygon(vector<Point> &set) {
        sort(set.begin(), set.end());
        v = vector<Point>();
        v.push_back(set[0]);
        v.push_back(set[1]);
        for (int i = 2; i < static_cast<int>(set.size()); ++ i) {
            while (cross_product(v[v.size() - 2], v[v.size() - 1], set[i]) >= 0) {
                v.pop_back();
            }
            v.push_back(set[i]);
        }
        for (int i = set.size() - 2; i >= 0; -- i) {
            while (cross_product(v[v.size() - 2], v[v.size() - 1], set[i]) >= 0) {
                v.pop_back();
            }
            v.push_back(set[i]);
        }
    }
} moveable, obstacles[MAX_M];

inline bool intersect(const Point &a, const Point &b, const Point &c, const Point &d) {
    ///check whether segments (a, b) and (c, d) intersect

    ///if a point is contained in the other segment
    if (fabs(get_dist(a, c) + get_dist(c, b) - get_dist(a, b)) < EPSILON) {
        return true;
    }
    if (fabs(get_dist(a, d) + get_dist(d, b) - get_dist(a, b)) < EPSILON) {
        return true;
    }
    if (fabs(get_dist(c, a) + get_dist(a, d) - get_dist(c, d)) < EPSILON) {
        return true;
    }
    if (fabs(get_dist(c, b) + get_dist(b, d) - get_dist(c, d)) < EPSILON) {
        return true;
    }
    ///if they are parallel
    if ((a.x - b.x) * (c.y - d.y) == (c.x - d.x) * (a.y - b.y)) {
        return false;
    }
    double x = ((c.x * d.y - d.x * c.y) * (a.x - b.x) - (a.x * b.y - b.x * a.y) * (c.x - d.x)) / ((a.y - b.y) * (c.x - d.x) - (c.y - d.y) * (a.x - b.x));
    double y = ((a.x * b.y - b.x * a.y) * (c.y - d.y) - (c.x * d.y - d.x * c.y) * (a.y - b.y)) / ((a.x - b.x) * (c.y - d.y) - (c.x - d.x) * (a.y - b.y));
    Point p(x, y);
    return fabs(get_dist(a, b) - get_dist(a, p) - get_dist(p, b)) < EPSILON && fabs(get_dist(c, d) - get_dist(c, p) - get_dist(p, d)) < EPSILON;
}

bool is_free(const Point &a, const Point &b, pair<int, int> pos_a, pair<int, int> pos_b) {
    ///check if segment (a, b) passes through any other segment
    for (int i = 0; i < m; ++ i) {
        for (int j = 0; j + 1 < static_cast<int>(obstacles[i].v.size()); ++ j) {
            if (pos_a.first == i && (pos_a.second == j || pos_a.second == j + 1)) {
                continue;
            }
            if (pos_b.first == i && (pos_b.second == j || pos_b.second == j + 1)) {
                continue;
            }
            if (intersect(a, b, obstacles[i].v[j], obstacles[i].v[j + 1])) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    ifstream fin("robot.in");
    ofstream fout("robot.out");
    int n, k = 0; double x = 5000.1, y = 5000.1, xfinal, yfinal;
    fin >> n;
    moveable = Polygon(n);
    for (int i = 0; i < n; ++ i) {
        fin >> moveable.v[i].x >> moveable.v[i].y;
        x = min(x, moveable.v[i].x);
        y = min(y, moveable.v[i].y);
    }
    points[++ k] = Point(x, y); position[k] = make_pair(-1, -1);
    fin >> m;
    for (int i = 0; i < m; ++ i) {
        int num; double xprime, yprime;
        fin >> num;
        vector<Point> v;
        for (int j = 0; j < num; ++ j) {
            fin >> xprime >> yprime;
            for (int k = 0; k < n; ++ k) {
                v.push_back(Point(xprime + x - moveable.v[k].x, yprime + y - moveable.v[k].y));
            }
        }
        obstacles[i] = Polygon(v);
        for (int j = 0; j + 1 < static_cast<int>(obstacles[i].v.size()); ++ j) {
            points[++ k] = obstacles[i].v[j];
            position[k] = make_pair(i, j);
        }
    }
    fin >> xfinal >> yfinal;
    points[++ k] = Point(xfinal, yfinal); position[k] = make_pair(-1, -1);
    for (int i = 2; i <= k; ++ i) {
        dist[i] = INFINITE;
    }
    dist[1] = 0;

    vector< pair<int, double> > heap;
    heap.push_back(make_pair(1, 0.0));
    while (!heap.empty()) {
        int current = heap.front().first; double current_dist = heap.front().second;
        pop_heap(heap.begin(), heap.end(), cmp);
        heap.pop_back();
        if (current == k) {
            fout << current_dist << "\n";
            return 0;
        }
        for (int i = 1; i <= k; ++ i) {
            if (i != current && dist[i] > current_dist + get_dist(points[current], points[i]) && is_free(points[i], points[current], position[i], position[current])) {
                dist[i] = current_dist + get_dist(points[current], points[i]);
                heap.push_back(make_pair(i, dist[i]));
                push_heap(heap.begin(), heap.end(), cmp);
            }
        }
    }
    fout << "-1\n";
    return 0;
}