Cod sursa(job #843290)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 18:08:18
Problema Robot Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.93 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <vector>
#define maxn 20
#define maxm 27
#define inf 0x3f3f3f3f
#define mp make_pair
 
using namespace std;
 
struct punct {
    int x, y;
};
 
struct segm {
    punct a, b;
};
 
int n, m;
int i, j;
punct robot[maxn], p1, p2;
int nr[maxm], nr_nou[maxm];
punct polig[maxm][256], polig_nou[maxm][256];
punct ref, start, stop; 
vector <pair<int, int> > g[maxm][256];
vector <double> cst[maxm][256];
int i1, i2, jj1, jj2;
double cmin[maxm][256];
int usd[maxm][256];
 
bool cmp(segm a, segm b) {
    if (atan2(a.b.y - a.a.y, a.b.x - a.a.x) < atan2(b.b.y - b.a.y, b.b.x - b.a.x))
        return true;
    return false;
}
 
inline void det_dr_sus(punct polig[], int n, punct &dr_sus) {
    int i;
    dr_sus = polig[1];
    for (i = 2; i <= n; i++) 
        if (polig[i].y > dr_sus.y || (polig[i].y == dr_sus.y && polig[i].x > dr_sus.x))
            dr_sus = polig[i];
}
 
inline void det_st_jos(punct polig[], int n, punct &st_jos) {
    int i;
    st_jos = polig[1];
    for (i = 2; i <= n; i++) 
        if (polig[i].y < st_jos.y || (polig[i].y == st_jos.y && polig[i].x < st_jos.x))
            st_jos = polig[i];
}
 
void make_new_polig(int ind) {
    int i, nrt, tx, ty;
    punct ant, dr_sus, st_jos, ref_copy;
    segm t[256];
 
    nrt = 0;
    for (i = n + 1; i > 1; i--) {
        nrt++;
        t[nrt].a = robot[i]; t[nrt].b = robot[i - 1];
    }
 
    for (i = 1; i <= nr[ind]; i++) {
        nrt++;
        t[nrt].a = polig[ind][i]; t[nrt].b = polig[ind][i + 1];
    }
 
 
    sort(t + 1, t + nrt + 1, cmp);  
 
    ant.x = ant.y = 0;
    nr_nou[ind] = nrt;
 
    for (i = 1; i <= nrt; i++) {
        polig_nou[ind][i].x = ant.x + (t[i].b.x - t[i].a.x);
        polig_nou[ind][i].y = ant.y + (t[i].b.y - t[i].a.y);
        ant = polig_nou[ind][i];
    }
 
    det_dr_sus(robot, n, dr_sus);
    det_st_jos(polig[ind], nr[ind], st_jos);
         
    tx = st_jos.x - dr_sus.x; 
    ty = st_jos.y - dr_sus.y;
 
    ref_copy.x = ref.x + tx;
    ref_copy.y = ref.y + ty;
 
    det_st_jos(polig_nou[ind], nr_nou[ind], st_jos);
 
    tx = ref_copy.x - st_jos.x;
    ty = ref_copy.y - st_jos.y;
 
    for (i = 1; i <= nr_nou[ind]; i++) {
        polig_nou[ind][i].x += tx;
        polig_nou[ind][i].y += ty;
    }
 
    polig_nou[ind][nr_nou[ind] + 1] = polig_nou[ind][1];
 
}
 
inline int det(punct a, punct b, punct c) {
    return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y);
}
 
inline bool on_segment(punct p, punct p1, punct p2) {
    int xmin, xmax, ymin, ymax;
    xmin = min(p1.x, p2.x); xmax = max(p1.x, p2.x);
    ymin = min(p1.y, p2.y); ymax = max(p1.y, p2.y);
    if (det(p, p1, p2) == 0 && p.x >= xmin && p.x <= xmax && p.y >= ymin && p.y <= ymax)
        return 1;
    return 0;
}
 
inline int polig_area(punct polig[], int n) {
    int area = 0, i;
    for (i = 1; i <= n; i++)
        area = area + (polig[i].x * polig[i + 1].y - polig[i].y * polig[i + 1].x);
    return abs(area);
}
 
inline bool point_in_poly(punct p, punct polig[], int n) {
    int i, area, tr_area;
    for (i = 1; i <= n; i++)
        if (on_segment(p, polig[i], polig[i + 1]))
            return 0;
 
    area = polig_area(polig, n);
    tr_area = 0;
 
    for (i = 1; i <= n; i++) 
        tr_area = tr_area + abs(det(polig[i], polig[i + 1], p));
 
    if (tr_area == area)
        return 1;
    return 0;
     
}
 
int sdet(punct a, punct b, punct c) {
    int t = det(a, b, c);
    if (t < 0)
        return -1;
    if (t > 0)
        return 1;
    return 0;
}
 
inline int intersect(punct p1, punct p2, punct q1, punct q2) {
    int a, b, c, d;
    int xmin1, xmax1, ymin1, ymax1;
    int xmin2, xmax2, ymin2, ymax2;
 
    xmin1 = min(p1.x, p2.x);
    xmin2 = min(q1.x, q2.x);
    xmax1 = max(p1.x, p2.x);
    xmax2 = max(q1.x, q2.x);
 
    ymin1 = min(p1.y, p2.y);
    ymin2 = min(q1.y, q2.y);
    ymax1 = max(p1.y, p2.y);
    ymax2 = max(q1.y, q2.y);
 
    if (xmax1 < xmin2 || xmax2 < xmin1 || ymax1 < ymin2 || ymax2 < ymin1)
        return 0;
 
    a = sdet(p1, p2, q1);
    b = sdet(p1, p2, q2);
    c = sdet(q1, q2, p1);
    d = sdet(q1, q2, p2);
    if (a * b * c * d == 0)
        return -1;
    if (a * b == -1 && c * d == -1)
        return 1;
    return 0;
}
 
inline bool intersection_test(punct p1, punct p2) {
 
    int i, j, k, verif, val;
    for (i = 1; i <= m; i++) {
        verif = 0;
        for (j = 1; j <= nr_nou[i]; j++) {
            val = intersect(p1, p2, polig_nou[i][j], polig_nou[i][j + 1]); 
            if (val > 0) 
                return 0;
         
            if (val < 0) 
                verif = 1;
        }
 
        if (verif == 1) {
            for (j = 1; j <= nr_nou[i]; j++)
                for (k = j + 1; k <= nr_nou[i]; k++) {
                    val = intersect(p1, p2, polig_nou[i][j], polig_nou[i][k]);
                    if (val > 0)
                        return 0;
                }
        }
    }
 
    return 1;   
}
 
inline bool good(punct p1, punct p2) {
    bool ok = 1;
    int i;
 
    for (i = 1; i <= m; i++) {
        if (point_in_poly(p1, polig_nou[i], nr_nou[i])) 
            ok = 0;
 
        if (point_in_poly(p2, polig_nou[i], nr_nou[i])) 
            ok = 0;
     
        if (ok == 0) 
            return 0;
    }
 
    if (intersection_test(p1, p2) == 0) 
        return 0;
 
    return 1;
}
 
inline double dist(punct p1, punct p2) {
    return (sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)));
}
 
inline void make_graph() {
    nr_nou[0] = 2;
    polig_nou[0][1] = start;
    polig_nou[0][2] = stop;
 
    for (i1 = 0; i1 <= m; i1++)
        for (i2 = 1; i2 <= nr_nou[i1]; i2++)
            for (jj1 = 0; jj1 <= m; jj1++)
                for (jj2 = 1; jj2 <= nr_nou[jj1]; jj2++) {
                    p1 = polig_nou[i1][i2];
                    p2 = polig_nou[jj1][jj2];
                    if (good(p1, p2)) {
                        g[i1][i2].push_back(mp(jj1, jj2));
                        cst[i1][i2].push_back(dist(polig_nou[i1][i2], polig_nou[jj1][jj2]));
                    }
                }
}
 
void dijkstra(int x, int y) {
    int i, j, ok, ind1, ind2;
    double smin, ct;
    for (i = 0; i <= m; i++)
        for (j = 0; j <= nr_nou[i]; j++)
            cmin[i][j] = 2000000000;
    memset(usd, 0, sizeof(usd));
    cmin[x][y] = 0;
 
    ok = 1;
    while (ok) {
        ok = 0;
        smin = inf;
 
        for (i = 0; i <= m; i++)
            for (j = 1; j <= nr_nou[i]; j++)
                if (!usd[i][j] && cmin[i][j] < smin) {
                    smin = cmin[i][j];
                    x = i; y = j;
                    ok = 1;
                }
         
        if (ok == 0)
            break;
        usd[x][y] = 1;
 
        for (i = 0; i < g[x][y].size(); i++) {
            ind1 = g[x][y][i].first;
            ind2 = g[x][y][i].second;
            ct = cst[x][y][i];
 
            if (cmin[x][y] + ct < cmin[ind1][ind2]) 
                cmin[ind1][ind2] = cmin[x][y] + ct;
        }
    }
}
 
 
int main() {
    freopen("robot.in", "r", stdin);
    freopen("robot.out", "w", stdout);
 
    scanf("%d", &n);
 
    ref.x = ref.y = inf;
    for (i = 1; i <= n; i++) {
         
        scanf("%d%d", &robot[i].x, &robot[i].y);
        ref.x = min(ref.x, robot[i].x);
        ref.y = min(ref.y, robot[i].y);
    }
    start = ref;
    robot[n + 1] = robot[1];
 
    scanf("%d", &m);
    for (i = 1; i <= m; i++) {
        scanf("%d", &nr[i]);
        for (j = 1; j <= nr[i]; j++)
            scanf("%d%d", &polig[i][j].x, &polig[i][j].y);
        polig[i][nr[i] + 1] = polig[i][1];
    }
 
    scanf("%d%d", &stop.x, &stop.y);
 
    for (i = 1; i <= m; i++) 
        make_new_polig(i);
 
    make_graph();
    dijkstra(0, 1);
 
    printf("%.2lf\n", cmin[0][2]);
 
    return 0;
}