Cod sursa(job #3348072)

Utilizator dummy-accdummy acc dummy-acc Data 19 martie 2026 15:55:34
Problema Robot Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.16 kb
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

struct Pt { ll x, y; };
static inline ll cross2(Pt a, Pt b) { return a.x*b.y - a.y*b.x; }

static const int MP = 26;
static const int MV = 262;
static const int MAXN = 520;

int nobs;
int pn[MP];
Pt  pvI[MP][MV];

double pvx[MP][MV], pvy[MP][MV]; 
double pnx[MP][MV], pny[MP][MV];
ll bbx0[MP], bbx1[MP], bby0[MP], bby1[MP];

static void precomp(int i) {
    int n = pn[i];
    ll x0, x1, y0, y1;
    x0 = x1 = pvI[i][0].x;
    y0 = y1 = pvI[i][0].y;
    for (int j = 0; j < n; j++) {
        ll px = pvI[i][j].x, py = pvI[i][j].y;
        if (px < x0) x0 = px; if (px > x1) x1 = px;
        if (py < y0) y0 = py; if (py > y1) y1 = py;
        pvx[i][j] = (double)px;
        pvy[i][j] = (double)py;
        int k = j + 1; if (k == n) k = 0;
        pnx[i][j] = (double)(-(pvI[i][k].y - py));
        pny[i][j] = (double)(pvI[i][k].x - px);
    }
    bbx0[i] = x0; bbx1[i] = x1;
    bby0[i] = y0; bby1[i] = y1;
}

static void ensure_ccw(Pt* p, int n) {
    ll a2 = 0;
    for (int i = 0; i < n; i++) { int j=(i+1)%n; a2 += p[i].x*p[j].y - p[j].x*p[i].y; }
    if (a2 < 0) for (int i = 0; i < n/2; i++) swap(p[i], p[n-1-i]);
}
static int remove_collinear(Pt* p, int n) {
    if (n <= 2) return n;
    Pt tmp[300]; int m = 0;
    for (int i = 0; i < n; i++) {
        int prev = (i - 1 + n) % n, next = (i + 1) % n;
        ll cr = (p[i].x - p[prev].x) * (ll)(p[next].y - p[prev].y) -
                (p[i].y - p[prev].y) * (ll)(p[next].x - p[prev].x);
        if (cr != 0) tmp[m++] = p[i];
    }
    memcpy(p, tmp, m * sizeof(Pt));
    return m;
}
static void reorder_bottom(Pt* p, int n) {
    int pos = 0;
    for (int i = 1; i < n; i++)
        if (p[i].y < p[pos].y || (p[i].y == p[pos].y && p[i].x < p[pos].x)) pos = i;
    if (pos) {
        Pt tmp[300]; memcpy(tmp, p, n*sizeof(Pt));
        for (int i = 0; i < n; i++) p[i] = tmp[(i+pos)%n];
    }
}
static int mink_sum(Pt* A, int sa, Pt* B, int sb, Pt* out) {
    sa = remove_collinear(A, sa);
    sb = remove_collinear(B, sb);
    reorder_bottom(A, sa); reorder_bottom(B, sb);
    A[sa]=A[0]; A[sa+1]=A[1]; B[sb]=B[0]; B[sb+1]=B[1];
    int i=0, j=0, cnt=0;
    while (i < sa || j < sb) {
        out[cnt++] = {A[i].x+B[j].x, A[i].y+B[j].y};
        Pt da = {A[i+1].x-A[i].x, A[i+1].y-A[i].y};
        Pt db = {B[j+1].x-B[j].x, B[j+1].y-B[j].y};
        ll cr = cross2(da, db);
        if      (cr > 0) i++;
        else if (cr < 0) j++;
        else            { i++; j++; }
    }
    cnt = remove_collinear(out, cnt);
    return cnt;
}

Pt  nd[MAXN];
int nn;
bool vld[MAXN];
double gd[MAXN];
bool vis[MAXN];
struct Edge { int to; double w; int nxt; };
Edge el[MAXN * MAXN];
int  hd[MAXN];
int  etot;

int main() {
    freopen("robot.in", "r", stdin);
    freopen("robot.out", "w", stdout);

    int N; scanf("%d", &N);
    Pt robot[12];
    for (int i = 0; i < N; i++) scanf("%lld%lld", &robot[i].x, &robot[i].y);

    ll rx = robot[0].x, ry = robot[0].y;
    for (int i = 1; i < N; i++) { if(robot[i].x<rx) rx=robot[i].x; if(robot[i].y<ry) ry=robot[i].y; }

    Pt negd[12];
    for (int i = 0; i < N; i++) negd[i] = {-(robot[i].x-rx), -(robot[i].y-ry)};
    for (int i = 0; i < N/2; i++) swap(negd[i], negd[N-1-i]);
    ensure_ccw(negd, N);

    int M; scanf("%d", &M);
    nobs = M;
    for (int oi = 0; oi < M; oi++) {
        int K; scanf("%d", &K);
        Pt obs[260];
        for (int j = 0; j < K; j++) scanf("%lld%lld", &obs[j].x, &obs[j].y);
        ensure_ccw(obs, K);
        Pt B[14]; memcpy(B, negd, N*sizeof(Pt));
        pn[oi] = mink_sum(obs, K, B, N, pvI[oi]);
        precomp(oi);
    }

    ll tx, ty; scanf("%lld%lld", &tx, &ty);

    nn = 0;
    nd[nn++] = {rx, ry};
    for (int i = 0; i < M; i++)
        for (int j = 0; j < pn[i]; j++)
            nd[nn++] = pvI[i][j];
    nd[nn++] = {tx, ty};

    for (int i = 0; i < nn; i++) {
        vld[i] = true;
        Pt p = nd[i];
        for (int j = 0; j < nobs; j++) {
            if (p.x < bbx0[j] | p.x > bbx1[j] | p.y < bby0[j] | p.y > bby1[j]) continue;
            double dpx = p.x, dpy = p.y;
            int n = pn[j]; bool inside = true;
            for (int k = 0; k < n; k++) {
                if ((dpx - pvx[j][k]) * pnx[j][k] + (dpy - pvy[j][k]) * pny[j][k] <= 0)
                { inside = false; break; }
            }
            if (inside) { vld[i] = false; break; }
        }
    }
    if (!vld[0] || !vld[nn-1]) { puts("-1"); return 0; }

    memset(hd, -1, nn * sizeof(int));
    etot = 0;

    for (int i = 0; i < nn; i++) {
        if (!vld[i]) continue;
        const double ax = (double)nd[i].x, ay = (double)nd[i].y;
        const ll iax = nd[i].x, iay = nd[i].y;

        for (int j = i + 1; j < nn; j++) {
            if (!vld[j]) continue;

            const double bx = (double)nd[j].x, by = (double)nd[j].y;
            const double dx = bx - ax, dy = by - ay;

            ll sx0, sx1, sy0, sy1;
            if (iax < nd[j].x) { sx0 = iax; sx1 = nd[j].x; }
            else               { sx0 = nd[j].x; sx1 = iax; }
            if (iay < nd[j].y) { sy0 = iay; sy1 = nd[j].y; }
            else               { sy0 = nd[j].y; sy1 = iay; }

            bool blk = false;
            for (int k = 0; k < nobs; k++) {
                if (sx1 < bbx0[k] | sx0 > bbx1[k] | sy1 < bby0[k] | sy0 > bby1[k])
                    continue;

                const int ne = pn[k];
                const double *vx = pvx[k], *vy = pvy[k];
                const double *nx = pnx[k], *ny = pny[k];
                double t_en = 0, t_ex = 1;
                bool escaped = false;

                for (int e = 0; e < ne; e++) {
                    double alpha = (ax - vx[e]) * nx[e] + (ay - vy[e]) * ny[e];
                    double beta  = dx * nx[e] + dy * ny[e];

                    if (__builtin_expect(beta == 0, 0)) {
                        if (alpha <= 0) { escaped = true; break; }
                        continue;
                    }
                    double t = -alpha / beta;
                    if (beta > 0) {
                        if (t > t_en) t_en = t;
                    } else {
                        if (t < t_ex) t_ex = t;
                    }
                    if (t_en > t_ex + 1e-9) { escaped = true; break; }
                }
                if (!escaped && t_en + 1e-9 < t_ex) { blk = true; break; }
            }
            if (!blk) {
                double w = sqrt(dx*dx + dy*dy);
                el[etot] = {j, w, hd[i]}; hd[i] = etot++;
                el[etot] = {i, w, hd[j]}; hd[j] = etot++;
            }
        }
    }

    for (int i = 0; i < nn; i++) { gd[i] = 1e18; vis[i] = false; }
    gd[0] = 0.0;
    int goal = nn - 1;
    for (int it = 0; it < nn; it++) {
        int u = -1; double best = 1e18;
        for (int j = 0; j < nn; j++)
            if (!vis[j] && gd[j] < best) { best = gd[j]; u = j; }
        if (u < 0 || u == goal) break;
        vis[u] = true;
        for (int e = hd[u]; e != -1; e = el[e].nxt) {
            double nd2 = gd[u] + el[e].w;
            if (nd2 < gd[el[e].to]) gd[el[e].to] = nd2;
        }
    }

    if (gd[goal] > 1e17) puts("-1");
    else printf("%.2f\n", gd[goal]);
    return 0;
}