Cod sursa(job #159345)

Utilizator city_guy91alex isip city_guy91 Data 14 martie 2008 08:21:33
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.34 kb
#include <cstdio>      
#include <cstdlib>      
#include <cstring>      
#include <math.h>      
#include <vector>      
#include <algorithm>      
     
using namespace std;      
     
#define sz(a) int((a).size())      
#define pb push_back      
#define mp make_pair      
#define x first      
#define y second      
#define punct pair<int, int>      
#define punct2 pair<double, double>      
#define tr(c, it) for (typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)      
#define all(c) (c).begin(), (c).end()      
     
#define inf 1e9      
#define Pmax 30000      
     
punct finish;      
vector< punct > robot;      
vector< vector< punct> > obstacol;      
     
char viz[Pmax];      
int st[Pmax];      
     
vector< punct > v;      
punct2 inter;      
     
void readdata()      
{      
    freopen("robot.in", "r", stdin);      
    freopen("robot.out", "w", stdout);      
     
    int i, j, a, b, n, m;      
    vector<punct> aux;      
     
    scanf("%d", &n);      
    for (i = 0; i < n; ++i)      
    {      
        scanf("%d %d", &a, &b);      
        robot.pb( mp(a, b) );      
    }      
     
    scanf("%d", &m);      
    for (i = 1; i <= m; ++i)      
    {      
        scanf("%d", &n);      
        for (aux.clear(), j = 0; j < n; ++j)      
        {      
            scanf("%d %d", &a, &b);      
            aux.pb( mp(a, b) );      
        }      
        obstacol.pb(aux);      
    }      
     
    scanf("%d %d", &finish.x, &finish.y);      
}      
     
int sign(punct a, punct b, punct c)      
{      
    int prod = (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y);      
    return (prod == 0 ? 0 : prod < 0 ? -1 : 1);      
}      
     
void convex_hull(vector< punct > &v)      
{      
    int i, p = 1, n;      
    vector< punct> aux;      
     
    sort( all(v) );      
    v.resize( unique(all(v)) - v.begin() );      
     
    n = sz(v);      
    memset(viz, 0, sizeof(viz));      
    st[ st[0] = 1 ] = 0;      
    for (i = 1; i >= 0; i += (p = (i == n-1) ? -p : p))      
        if (!viz[i])      
        {      
            while (st[0] >= 2 && sign(v[i], v[st[ st[0] ]], v[st[ st[0]-1 ]]) <= 0)      
                    viz[ st[ st[0]-- ] ] = 0;      
            viz[ st[++st[0]] = i ] = 1;      
        }      
    for (i = 1; i < st[0]; ++i)      
        aux.pb(v[st[i]]);      
    v = aux;      
}      
     
void refa_obstacol(vector< punct > &v)      
{      
    int i, j, lim = sz(v);      
          
    for (i = 0; i < lim; ++i)      
        for (j = 0; j < sz(robot); ++j)      
            v.pb( mp(v[i].x + robot[0].x - robot[j].x, v[i].y + robot[0].y - robot[j].y) );      
    convex_hull(v);      
}      
     
void refa_finish()      
{      
    int best = robot[0].y;      
    tr(robot, it) best = min(best, it->y);      
    finish.y += robot[0].y-best;      
}      
     
inline double sqr(int a) { return double(a*a); }      
     
int apartine(punct a, punct b, punct c)      
{      
    punct p1 = min(b, c), p2 = max(b, c);      
     
    return ((a.y-p1.y)*(p2.x-p1.x) == (a.x-p1.x)*(p2.y-p1.y) && a >= p1 && a <= p2);      
}      
     
int coliniar(punct a, punct b, punct c)      
{      
    return (a.y-b.y)*(c.x-b.x) == (a.x-b.x)*(c.y-b.y);      
}      
     
int contur(punct a, vector< punct > &v)      
{      
    for (int i = 0; i < sz(v)-1; ++i)      
        if (apartine(a, v[i], v[i+1]))      
            return 1;      
    return 0;      
}      
     
int arie_poligon(vector< punct > &v)      
{      
    int ret = 0, i;      
    for (i = 0; i < sz(v)-1; ++i)      
        ret += v[i].x*v[i+1].y - v[i+1].x*v[i].y;      
    return abs(ret);      
}      
     
int arie_punct(punct a, vector< punct > &v)      
{      
    vector< punct > aux;      
    int ret = 0, i;      
     
    for (i = 0; i < sz(v)-1; ++i)      
    {      
        aux.clear();      
        aux.pb(v[i]), aux.pb(v[i+1]), aux.pb(a); aux.pb(v[i]);      
        ret += arie_poligon(aux);      
    }      
    return ret;      
}      
     
int intersection(punct a, punct b, punct c, punct d)      
{      
    double A, B, C, A2, B2, C2, det;      
     
    A = b.y-a.y;      
    B = a.x-b.x;      
    C = -a.y*(b.x-a.x) + a.x*(b.y-a.y);      
     
    A2 = d.y-c.y;      
    B2 = c.x-d.x;      
    C2 = -c.y*(d.x-c.x) + c.x*(d.y-c.y);      
     
    det = A*B2 - B*A2;      
    if (det == 0) return 0;      
    inter = mp( (B2*C - B*C2)/det, (A*C2 - A2*C)/det );      
     
    return (sign(c, b, a) * sign(d, b, a) <= 0 && sign(a, c, d) * sign(b, c, d) <= 0);      
}      
     
int intersecteaza(punct a, punct b, vector< punct > &v)      
{      
    int i;      
     
    //cazul in care a si b apartin dreptei suport a unei laturi      
    for (i = 0; i < sz(v)-1; ++i)      
        if (coliniar(a, v[i], v[i+1]) && coliniar(b, v[i], v[i+1]))      
            return 0;      
     
    //afla care din puncte se afla pe conturul poligonului      
    char v1 = contur(a, v), v2 = contur(b, v);      
    if (v1 && v2) return 1;      
     
    //cazul in care un punct apartine interiorului poligonului      
    int ap = arie_poligon(v), a1 = arie_punct(a, v), a2 = arie_punct(b, v);      
    if (a1 == ap && !v1) return 1;      
    if (a2 == ap && !v2) return 1;      
     
    vector< punct2 > aux;      
    for (i = 0; i < sz(v)-1; ++i)      
        if (intersection(a, b, v[i], v[i+1]))      
            aux.pb(inter);      
    sort(all(aux));      
    aux.resize( unique(all(aux)) - aux.begin() );      
     
    return sz(aux) > 1;      
}      
     
double afla_distanta(punct a, punct b)      
{      
    double ret = sqrt(sqr(a.x-b.x) + sqr(a.y-b.y));      
    int i;      
     
    if (a == b) return ret;      
    for (i = 0; i < sz(obstacol); ++i)      
        if (intersecteaza(a, b, obstacol[i]))      
            return inf;      
    return ret;      
}      
     
void solve()      
{      
    int i, j;      
     
    //redu robotul la un singur punct;      
    sort(all(robot));      
    for (i = 0; i < sz(obstacol); ++i)      
        refa_obstacol(obstacol[i]);      
    refa_finish();      
     
    //afla punctele ce pot fi vizitate si matricea de adiacenta      
    v.pb(robot[0]);      
    for (i = 0; i < sz(obstacol); ++i)      
        for (j = 0; j < sz(obstacol[i]); ++j)      
            v.pb(obstacol[i][j]);      
    v.pb(finish);      
     
    vector< vector< double > > c( sz(v), sz(v) );      
     
    for (i = 0; i < sz(obstacol); ++i)      
        obstacol[i].pb( obstacol[i][0] );      
     
    for (i = 0; i < sz(v); ++i)      
        for (j = 0; j < sz(v); ++j)      
            c[i][j] = afla_distanta(v[i], v[j]);      
     
    //afla drumul cel mai scurt si afiseaza      
    int n = sz(v)-1;      
    vector< double > d(n+1, inf);      
    vector< char > viz(n+1, 0);      
     
    double best;      
    int poz;      
     
    d[0] = 0;      
    while (!viz[n])      
    {      
        best = inf;      
        for (i = 0; i <= n; ++i)      
            if (!viz[i] && d[i] < best)      
            {      
                best = d[i];      
                poz = i;      
            }      
        viz[poz] = 1;      
        for (i = 0; i <= n; ++i)      
            d[i] = min(d[i], best + c[poz][i]);      
    }      
    printf("%lf\n", d[n]);      
}      
     
int main()      
{      
    readdata();      
    solve();      
    return 0;      
}