Cod sursa(job #1489317)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 20 septembrie 2015 23:05:04
Problema Robot Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.17 kb
#include <bits/stdc++.h>

#define mp make_pair
#define eb emplace_back
#define pb push_back
#define sz(x) (int(x.size()))
#define st first
#define nd second

using namespace std;

typedef pair<int, int> PII;
typedef int64_t i64;

const int MMAX = 30, GMAX = 2600;
const double eps = 1e-3;

int N, M;
bool inqueue[GMAX];
double d[GMAX][GMAX], dist[GMAX];
PII refp, finish;
vector<PII> rbt, obs[MMAX], ST, good_vertices;
vector<int> G[GMAX];

i64 CrossProduct(PII A, PII B, PII C) {
    i64 ret = i64(A.st) * B.nd + i64(B.st) * C.nd + i64(C.st) * A.nd - i64(C.st) * B.nd - i64(A.st) * C.nd - i64(B.st) * A.nd;
    return ret;
}

struct Compare {
    bool operator()(const PII &A, const PII &B) const {
        return CrossProduct(refp, A, B) < 0;
    }
};

bool InsideObstacle(int pos, PII point) {
    int i;
    double parea = 0;

    for (i = 0; i < sz(obs[pos]); ++i) {
        parea += abs(CrossProduct(point, obs[pos][i], obs[pos][(i + 1) % sz(obs[pos])]) / double(2));
        if (CrossProduct(point, obs[pos][i], obs[pos][(i + 1) % sz(obs[pos])]) == 0)
            return false;
    }

    double area = 0;
    for (i = 0; i < sz(obs[pos]); ++i)
        area += CrossProduct({0, 0}, obs[pos][i], obs[pos][(i + 1) % sz(obs[pos])]);
    area = abs(area / 2);

    if (abs(parea - area) <= eps)
        return true;
    return false;
}

bool InsideAnyObstacle(PII point) {
    for (int i = 1; i <= M; ++i)
        if (InsideObstacle(i, point))
            return true;
    return false;
}

void ConvexHull(int pos) {
    sort(obs[pos].begin(), obs[pos].end());
    obs[pos].erase(unique(obs[pos].begin(), obs[pos].end()), obs[pos].end());

    refp = obs[pos][0];

    sort(obs[pos].begin() + 1, obs[pos].end(), Compare());

    ST.clear();
    ST.eb(obs[pos][0]);
    ST.eb(obs[pos][1]);

    for (int i = 2; i < sz(obs[pos]); ++i) {
        if (CrossProduct(ST[ST.size() - 2], ST[ST.size() - 1], obs[pos][i]) == 0) {
            ST.pop_back();
            ST.eb(obs[pos][i]);
        } else if (CrossProduct(ST[ST.size() - 2], ST[ST.size() - 1], obs[pos][i]) < 0) {
            ST.eb(obs[pos][i]);
        } else {
            while (CrossProduct(ST[ST.size() - 2], ST[ST.size() - 1], obs[pos][i]) >= 0 && ST.size() > 1)
                ST.pop_back();
            ST.eb(obs[pos][i]);
        }
    }

    obs[pos] = ST;
}

int Sign(i64 value) {
    if (value < 0)
        return -1;
    if (value > 0)
        return 1;
    return 0;
}

bool Intersect(PII A, PII B, PII C, PII D) {
    if (max(A.st, B.st) < min(C.st, D.st))
        return 0;
    if (min(A.st, B.st) > max(C.st, D.st))
        return 0;
    if (max(A.nd, B.nd) < min(C.nd, D.nd))
        return 0;
    if (min(A.nd, B.nd) > max(C.nd, D.nd))
        return 0;

    int sgn1 = Sign(CrossProduct(A, B, C)) * Sign(CrossProduct(A, B, D));
    int sgn2 = Sign(CrossProduct(C, D, B)) * Sign(CrossProduct(C, D, A));

    return sgn1 < 0 && sgn2 < 0;
}

bool EdgeOK(int a, int b) {
    for (int i = 1; i <= M; ++i) {
        for (int j = 0; j < sz(obs[i]); ++j) {
            for (int k = j + 1; k < sz(obs[i]); ++k) {
                if (Intersect(good_vertices[a], good_vertices[b], obs[i][j], obs[i][k]))
                    return false;
            }
        }
    }
    return true;
}

int main() {
	ios_base::sync_with_stdio(false);
    freopen("robot.in", "r", stdin);
    freopen("robot.out", "w", stdout);
	freopen("robot.err", "w", stderr);

    int i, j, x, y, k;
    PII start = {1e9, 1e9};

    cin >> N;
    for (i = 1; i <= N; ++i) {
        cin >> x >> y;
        rbt.eb(mp(x, y));
        start.st = min(start.st, x);
        start.nd = min(start.nd, y);
    }

    cin >> M;
    for (i = 1; i <= M; ++i) {
        int cnt;
        cin >> cnt;
        for (j = 1; j <= cnt; ++j) {
            cin >> x >> y;
            obs[i].eb(mp(x, y));
        }
    }
    cin >> finish.st >> finish.nd;

    sort(rbt.begin(), rbt.end());

    for (i = 1; i <= M; ++i) {
        int limit = sz(obs[i]);
        for (j = 0; j < limit; ++j)
            for (k = 0; k < sz(rbt); ++k)
                obs[i].eb(mp(obs[i][j].st - rbt[k].st + rbt[0].st, obs[i][j].nd - rbt[k].nd + rbt[0].nd));
        ConvexHull(i);
    }

    good_vertices.eb(rbt[0]);
    int diff_x = rbt[0].st - start.st, diff_y = rbt[0].nd - start.nd;
    good_vertices.eb(mp(finish.st + diff_x, finish.nd + diff_y));

    for (i = 1; i <= M; ++i) {
        for (j = 0; j < sz(obs[i]); ++j)
            if (!InsideAnyObstacle(obs[i][j]))
                good_vertices.eb(obs[i][j]);
    }

    for (i = 0; i < sz(good_vertices) - 1; ++i) {
        for (j = i + 1; j < sz(good_vertices); ++j) {
            if (EdgeOK(i, j)) {
                G[i].eb(j);
                G[j].eb(i);
                d[i][j] = d[j][i] = sqrt(1LL * (good_vertices[i].st - good_vertices[j].st) * (good_vertices[i].st - good_vertices[j].st) + 1LL * (good_vertices[i].nd - good_vertices[j].nd) * (good_vertices[i].nd - good_vertices[j].nd));
            }
        }
    }

    for (i = 0; i < sz(good_vertices); ++i)
        dist[i] = 1e18;

    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> Q;
    Q.push({0, 0});
    dist[0] = 0;
    while (!Q.empty()) {
        auto now = Q.top();
        Q.pop();

        for (auto it : G[now.nd]) {
            if (dist[it] > dist[now.nd] + d[now.nd][it]) {
                dist[it] = dist[now.nd] + d[now.nd][it];
                Q.push({dist[it], it});
            }
        }
    }

    /*queue<int> Q;
    Q.push(0);
    dist[0] = 0;
    inqueue[0] = 1;
    while (!Q.empty()) {
        auto now = Q.front();
        Q.pop();
        inqueue[now] = 0;

        for (auto it : G[now]) {
            if (dist[it] > dist[now] + d[now][it]) {
                dist[it] = dist[now] + d[now][it];
                if (!inqueue[it])
                    Q.push(it);
            }
        }
    }*/

    if (InsideAnyObstacle(finish) || dist[1] >= 1e17) {
        assert(true);
        cout << "-1\n";
        return 0;
    }

    cout << fixed << setprecision(4) << dist[1] << '\n';
	return 0;
}