Cod sursa(job #2142455)

Utilizator dario2994Federico Glaudo dario2994 Data 25 februarie 2018 00:40:05
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.7 kb
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
    bool done_something = false;
    stringstream res;
    res << "[";
    for (; begin_iter != end_iter and counter; ++begin_iter) {
        done_something = true;
        counter--;
        res << *begin_iter << ", ";
    }
    string str = res.str();
    if (done_something) {
        str.pop_back();
        str.pop_back();
    }
    str += "]";
    return str;
}

vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
    vector<int> ord(size);
    for (int i = 0; i < size; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), compare);
    return ord;
}

template <typename T>
bool MinPlace(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool MaxPlace(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <typename Container>
int SZ(const Container& S) { return S.size(); }

template <typename S, typename T>
ostream& operator <<(ostream& out, const pair<S, T>& p) {
    out << "{" << p.first << ", " << p.second << "}";
    return out;
}

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& v) {
    out << "[";
    for (int i = 0; i < (int)v.size(); i++) {
        out << v[i];
        if (i != (int)v.size()-1) out << ", ";
    }
    out << "]";
    return out;
}

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file

    #define dbg_var(x) clog << #x  << ": " << x << endl;
    #define dbg_array(x, len) clog << #x << ": " << print_iterable(x, x+len, -1) << endl;
#else
    ifstream input_from_file("robot.in");
    #define cin input_from_file
    ofstream output_to_file("robot.out");
    #define cout output_to_file
    
    #define dbg_var(x)
    #define dbg_array(x, len)
#endif

///////////////////////////////////////////////////////////////////////////
//////////////////// DO NOT TOUCH BEFORE THIS LINE ////////////////////////
///////////////////////////////////////////////////////////////////////////

struct pt {
    int id;
    LL x,y;
    pt(LL x, LL y) : x(x), y(y) {}
    pt() : x(0), y(0) {}
    pt operator +(const pt& other) const { return {x+other.x, y+other.y}; }
    pt operator -(const pt& other) const { return {x-other.x, y-other.y}; }
    LL operator *(const pt& other) const { return x*other.x + y*other.y; }
    LL operator ^(const pt& other) const { return x*other.y - y*other.x; }
    bool operator <(const pt& other) const {
        if (x == other.x) return y < other.y;
        return x < other.x;
    }
    bool operator ==(const pt& other) const { return x == other.x and y == other.y; }
    double Norm() const { return sqrt(x*x + y*y); }
};

short int GetSign(LL x) { return (x > 0) - (x < 0); }

short int RelPos(const pt& O, const pt& A, const pt& B) {
    return GetSign((A-O)^(B-O));
}

vector<int> ConvexHull(const vector<pt>& points) {
    int N = points.size();
    vector<int> ord(N);
    for (int i = 0; i < N; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), [&points](int i, int j) { return points[i] < points[j]; });
    if (points[ord[0]] == points[ord.back()]) return {0};
    vector<int> aw, cw;
    aw.push_back(ord[0]);
    cw.push_back(ord[0]);
    for (int i = 1; i < N; i++) {
        int index = ord[i];
        pt V = points[index];
        while (aw.size() > 1 and RelPos(points[aw.rbegin()[1]], V, points[aw.back()]) != -1) {
            aw.pop_back();
        }
        aw.push_back(index);
        while(cw.size() > 1 and RelPos(points[cw.rbegin()[1]], V, points[cw.back()]) != 1) {
            cw.pop_back();
        }
        cw.push_back(index);
    }
    aw.pop_back();
    reverse(cw.begin(), cw.end());
    cw.pop_back();
    aw.insert(aw.end(), cw.begin(), cw.end());
    return aw;
}

const int MAXN = -1;

bool IsInside(pt P, const vector<pt>& pol) {
    for (int i = 0; i < (int)pol.size(); i++) {
        if (RelPos(pol[i], pol[(i+1) % pol.size()], P) <= 0) return false;
    }
    return true;
}

bool Intersecting(pt A, pt B, pt C, pt D) {
    return (RelPos(A, B, C) * RelPos(A, B, D) == -1 and RelPos(C, D, A)*RelPos(C, D, B) == -1);
}

bool IsOk(pt A, pt B, const vector<pt>& pol) {
    int N = pol.size();
    for (int i = 0; i < N; i++) {
        if (Intersecting(A, B, pol[i], pol[(i+1)%N])) return false;
        // if (RelPos(A, B, pol[i]) == 0 and !(A==pol[i]) and !(B==pol[i])) {
            // if (((A < pol[i] and pol[i] < B) or (B < pol[i] and pol[i] < A)) and
                // RelPos(A, B, pol[(i+1)%N])*RelPos(A, B, pol[(i+N-1)%N]) == -1) return false;
        // }
    }
    if (IsInside({(A+B).x/2, (A+B).y/2}, pol)) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Remove in problems with online queries!

    int N;
    cin >> N;
    vector<pt> robot(N);
    pt bv = {100000, 100000};
    for (int i = 0; i < N; i++) {
        cin >> robot[i].x >> robot[i].y;
        robot[i].x *= 2, robot[i].y *= 2;
        bv.x = min(bv.x, robot[i].x);
        bv.y = min(bv.y, robot[i].y);
    }
    pt start = robot[0];
    for (int i = 1; i < N; i++) robot[i] = robot[0]-robot[i];
    robot[0] = {0,0};
    // for (int i = 0; i < N; i++) cout << robot[i].x/2 << " " << robot[i].y/2 << "\n";
    int M;
    cin >> M;
    vector<vector<pt>> obstacles(M);
    vector<pt> all_pt;
    int points_num = 0;
    for (int i = 0; i < M; i++) {
        int P;
        cin >> P;
        vector<pt> pol;
        for (int j = 0; j < P; j++) {
            pt A;
            cin >> A.x >> A.y;
            A.x *= 2, A.y *= 2;
            for (int k = 0; k < N; k++) pol.push_back(A+robot[k]);
        }
        auto ch = ConvexHull(pol);
        for (int j = 0; j < (int)ch.size(); j++) {
            obstacles[i].push_back(pol[ch[j]]);
            // cout << "(" << pol[ch[j]].x/2 << ", " << pol[ch[j]].y/2 << "); ";
            obstacles[i].back().id = points_num;
            all_pt.push_back(obstacles[i].back());
            points_num++;
        }
        // cout << endl;
    }
    pt finish;
    cin >> finish.x >> finish.y;
    finish.x *= 2, finish.y *= 2;
    finish = finish +start-bv;
    // cout << start.x/2 << " " << start.y/2 << endl;
    // cout << finish.x/2 << " " << finish.y/2 << endl;

    start.id = points_num;
    finish.id = points_num+1;
    points_num += 2;
    all_pt.push_back(start);
    all_pt.push_back(finish);

    vector<vector<double>> dd(points_num, vector<double>(points_num));

    for (int i = 0; i < points_num; i++) {
        for (int j = i+1; j < points_num; j++) {
            bool works = true;
            for (int k = 0; k < M; k++) {
                if (!IsOk(all_pt[i], all_pt[j], obstacles[k])) {
                    works = false;
                    break;
                }
            }
            if (works) {
                dd[i][j] = dd[j][i] = (all_pt[i]-all_pt[j]).Norm();
            } else dd[i][j] = dd[j][i] = 1e10;
        }
    }


    vector<double> dist(points_num, 1e10);
    dist[points_num-2] = 0;
    priority_queue<pair<double, int>, vector<pair<double, int>>, std::greater<pair<double, int>>> q;
    q.push({0, points_num-2});
    while (!q.empty()) {
        auto pp = q.top();
        q.pop();
        int v = pp.second;
        double d = pp.first;
        if (d > dist[v]) continue;

        for (int i = 0; i < points_num; i++) {
            if (dist[i] > d + dd[v][i]) {
                dist[i] = d + dd[v][i];
                q.push({dist[i], i});
            }
        }
    }
    cout.precision(2);
    if (dist[points_num-1] > 1e9) cout << -1 << "\n";
    else cout << fixed << (dist[points_num-1]/2.0) << "\n";
}