Cod sursa(job #2002303)

Utilizator akaprosAna Kapros akapros Data 19 iulie 2017 13:26:50
Problema Robot Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.14 kb
#include <bits/stdc++.h>
#define maxN 12
#define maxM 27
#define maxV 252
#define inf 1000000000
#define pi 3.14159265359
#define e 1e-9
using namespace std;

FILE *fin = freopen("robot.in", "r", stdin);
FILE *fout = freopen("robot.out", "w", stdout);

/* ------------------------ In -------------------------- */
int n, m;
double d[maxV * maxN];
struct Point
{
    int x, y, id;
    bool operator < (const Point &ot) const
    {
        if (id > 0)
        {
            if (x == ot.x)
                return y < ot.y;
            return x < ot.x;
        }
        else
        {
            return d[id] > d[ot.id];
        }
    }
} v[maxN], piv, lst;
vector < Point > OldObst[maxM], Obst[maxM];
/* ------------------------ Sol -------------------------- */
bool vis[maxV * maxN];
bool inH[maxN * maxV];
vector < Point > nodes;
priority_queue < Point > H;
/* ---------------------------------------------------------------- */

int CrossProduct(Point O, Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
double dist(Point A, Point B)
{
    return sqrt(1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y));
}
int f(Point C, Point A, Point B)
{
    double a = (double)A.y - B.y,
           b = (double)B.x - A.x,
           c = (double)A.x * B.y - (double)A.y * B.x;
    if (a * C.x + b * C.y + c <= -e)
        return -1;
    if (a * C.x + b * C.y + c >= e)
        return 1;
    return 0;
}
double AngleRad(Point A, Point O, Point B)
{
    Point a = {A.x - O.x, A.y - O.y, 0},
          b = {B.x - O.x, B.y - O.y, 0};
    double u = fabs(atan2(a.x, a.y) - atan2(b.x, b.y));
    if (u > pi)
        u = 2 * pi - u;
    return u;
}
/* ---------------------------------------------------------------- */

void readRobCoord()
{
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &v[i].x, &v[i].y);
        v[i].id = i;
        piv.x = min(v[i].x, piv.x);
        piv.y = min(piv.y, v[i].y);
    }
}
void readObst(int idx)
{
    int sz;
    scanf("%d", &sz);
    OldObst[idx].resize(sz);
    for (int i = 0; i < sz; ++ i)
    {
        scanf("%d %d", &OldObst[idx][i].x, &OldObst[idx][i].y);
        OldObst[idx][i].id = i;
    }
}
/* ---------------------------------------------------------------- */
void ConvexHull(int idx)
{
    int N = Obst[idx].size();
    sort(Obst[idx].begin(), Obst[idx].end());
    memset(vis, 0, sizeof(vis));
    vector < Point > st;
    st.resize(2);
    st[0] = Obst[idx][0];
    st[1] = Obst[idx][1];
    int head = 1;
    vis[1] = true;
    for (int i = 0, p = 1; i >= 0; i += (p = (i == (N - 1) ? -p : p)))
    {
        if (vis[i]) continue;
        while (head >= 1 && CrossProduct(st[head - 1], st[head], Obst[idx][i]) <= 0)
        {
            vis[st[head --].id] = false;
            st.pop_back();
        }
        ++ head;
        st.push_back(Obst[idx][i]);
        vis[i] = true;
    }
    Obst[idx].resize(head + 1);
    int sz = 0;
    for (Point it : st)
        Obst[idx][sz ++] = it;
}

void updObst(int idx)
{
    int crt = 0;
    for (int i = 0; i < OldObst[idx].size(); ++ i)
        for (int j = 1; j <= n; ++ j)
            Obst[idx].push_back(Point{OldObst[idx][i].x - v[j].x + piv.x, OldObst[idx][i].y - v[j].y + piv.y, crt ++});
    ConvexHull(idx);
}
/* ---------------------------------------------------------------- */
bool inPoly(Point x, int idx)
{
    for (int i = 0; i < Obst[idx].size() - 1; ++ i)
    {
        int sgn = f(x, Obst[idx][i], Obst[idx][i + 1]),
            prv = (i == 0) ? (Obst[idx].size() - 2) : i - 1;
        if (sgn != f(Obst[idx][prv], Obst[idx][i], Obst[idx][i + 1]))
            return 0;
    }

    return 1;
}
bool IntersectsPoly(Point x, Point y, int idx)
{
    int hfPlane = 0, N = Obst[idx].size();
    if (abs(f(x, Obst[idx][N - 1], Obst[idx][0]) - f(y, Obst[idx][N - 1], Obst[idx][0])) >= 2)
        return 1;
    for (int i = 0; i < N - 1; ++ i)
    {
        if (i < N - 2 && (AngleRad(Obst[idx][i], Obst[idx][i + 1], x) <= pi / 2 && AngleRad(Obst[idx][i], Obst[idx][i + 1], y) <= pi / 2)
                && (AngleRad(Obst[idx][i + 1], Obst[idx][i], x) <= pi / 2 && AngleRad(Obst[idx][i + 1], Obst[idx][i], y) <= pi / 2)
                && (abs(f(x, Obst[idx][i], Obst[idx][i + 1]) - f(y, Obst[idx][i], Obst[idx][i + 1])) >= 2))
            return 1;
        if (AngleRad(Obst[idx][i], x, y) <= pi / 2 && AngleRad(Obst[idx][i], y, x) <= pi / 2)
        {
            int sgn = f(Obst[idx][i], x, y);
            if (abs(sgn - hfPlane) >= 2)
                return 1;
            else if (!hfPlane)
                hfPlane = sgn;
        }
    }

    if (inPoly(x, idx) || inPoly(y, idx))
        return 1;
    return 0;
}
/* ---------------------------------------------------------------- */
void BuildGraph()
{
    nodes.push_back(piv);
    for (int i = 1; i <= m; ++ i)
        for (int j = 0; j < Obst[i].size() - 1; ++ j)
            nodes.push_back(Obst[i][j]);
    nodes.push_back(lst);
}
bool Edge(Point x, Point y)
{
    for (int i = 1; i <= m; ++ i)
        if (IntersectsPoly(x, y, i))
            return 0;
    return 1;
}
void Dijkstra()
{
    int N = nodes.size();
    for (int i = 0; i < N; ++ i)
    {
        d[i] = (double)inf;
        nodes[i].id = -i - 1;
    }
    d[0] = 0;
    H.push(nodes[0]);
    while (!H.empty())
    {
        Point nod = H.top();
        H.pop();
        for (int i = 1; i < N; ++ i)
        {
            double add = dist(nodes[i], nod);
            if (d[i] > d[-nod.id - 1] + add && Edge(nodes[i], nod))
            {
                d[i] = d[-nod.id - 1] + add;
                if (!inH[i])
                {
                    inH[i] = 1;
                    H.push(nodes[i]);
                }
            }
        }
    }
}
int main()
{
    scanf("%d", &n);
    piv = {inf, inf};
    readRobCoord();
    scanf("%d", &m);
    for (int i = 1; i <= m; ++ i)
    {
        readObst(i);
        updObst(i);
    }
    scanf("%d %d", &lst.x, &lst.y);

    BuildGraph();
    Dijkstra();
    printf("%.9lf\n", d[nodes.size() - 1]);
    return 0;
}