Cod sursa(job #476209)

Utilizator freak93Adrian Budau freak93 Data 10 august 2010 11:30:48
Problema Robot Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.49 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<cassert>
#define x first
#define y second

using namespace std;

const char iname[]="robot.in";
const char oname[]="robot.out";
const int maxp=5000;
const int maxm=27;
const double inf=1e20;

ifstream f(iname);
ofstream g(oname);

class point
{
    public:
    int x,y;
    point():x(0),y(0){}
    point(int _x,int _y):x(_x),y(_y){}
    point operator-(point a) const
    {
        return point(x-a.x,y-a.y);
    }
    point operator+(point a) const
    {
        return point(x+a.x,y+a.y);
    }
    friend ifstream& operator>>(ifstream &f,point &a)
    {
        f>>a.x>>a.y;
        return f;
    }
    //vectori
    bool plane()
    {
        if(x<0||(x==0&&y<0))
            return false;
        return true;
    }
    friend bool operator<(point a,point b)
    {
        if(a.plane()!=b.plane())
            return a.plane()<b.plane();
        return a.y*b.x<b.y*a.x;
    }
    double dis(point b)
    {
        return sqrt(1.0*(x-b.x)*(x-b.x)+1.0*(y-b.y)*(y-b.y));
    }
    int area(point,point,point);
    bool not_inside(vector< point > a)
    {
        for(int i=1;i<(int)a.size();++i)
            if(area(a[i-1],a[i],*this)<=0)
                return true;
        if(area(a[a.size()-1],a[0],*this)<=0)
            return true;
        return false;
    }
    bool not_inside(vector< point > a[],int n)
    {
        for(int i=0;i<n;++i)
            if(not_inside(a[i])==false)
                return false;
        return true;
    }
}begin,end;

int area(point a,point b,point c)
{
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
int point::area(point a,point b,point c)
{
    return ::area(a,b,c);
}

vector< point > robot,obstacles[maxm],graph;

vector<pair<int,double> > E[maxp];

double dis[maxp],eps=1e-8;

int i,j,n,m,k,been[maxp];

queue<int> Q;

bool intersect(point a,point b,point c,point d)
{
    if(min(max(a.x,b.x),max(c.x,d.x))<max(min(a.x,b.x),min(c.x,d.x)))
        return 0;
    if(min(max(a.y,b.y),max(c.y,d.y))<max(min(a.y,b.y),min(c.y,d.y)))
        return 0;
    long long cros1=1LL*area(a,b,c)*area(a,b,d),cros2=1LL*area(c,d,a)*area(c,d,b);
    return cros1<0&&cros2<0;
}

bool is_posible(point a,point b)
{
    for(int i=0;i<m;++i)
        for(int j=0;j<(int)obstacles[i].size();++j)
            for(int k=j+1;k<(int)obstacles[i].size();++k)
            {
                if(intersect(a,b,obstacles[i][j],obstacles[i][k]))
                    return false;
            }
    return true;
}

vector<point> nfp(const vector< point >& base,const vector< point >& con)
{
    int i;
    vector< point > ans2aux,vectors;
    for(i=1;i<(int)base.size();++i)
        vectors.push_back(base[i-1]-base[i]);
    vectors.push_back(base[base.size()-1]-base[0]);
    for(i=1;i<(int)con.size();++i)
        vectors.push_back(con[i]-con[i-1]);
    vectors.push_back(con[0]-con[con.size()-1]);
    sort(vectors.begin(),vectors.end());

    point ex1=base[0],ex2=base[0],ex3=con[0];
    for(i=1;i<(int)base.size();++i)
    {
        if(base[i].y<ex1.y)
            ex1=base[i];
        if(base[i].x<ex2.x||(base[i].x==ex2.x&&base[i].y<ex2.y))
            ex2=base[i];
    }
    for(i=1;i<(int)con.size();++i)
        if(con[i].x>ex3.x||(con[i].x==ex3.x&&con[i].y>ex3.y))
            ex3=con[i];

    ex3=ex3-point(0,ex2.y-ex1.y);
    ans2aux.push_back(ex3);
    for(i=0;i<(int)vectors.size()-1;++i)
        ans2aux.push_back(ans2aux[i]+vectors[i]);
    vector<point> x;
    x.push_back(ans2aux[0]);
    x.push_back(ans2aux[1]);
    for(i=2;i<(int)ans2aux.size();++i)
    {
        if(x.size()>1&&area(x[x.size()-2],x[x.size()-1],ans2aux[i])==0)
            x.pop_back();
        x.push_back(ans2aux[i]);
    }
    return x;
}

int cmp(double a,double b)
{
    if(a+eps<b)
        return -1;
    if(b+eps<a)
        return 1;
    return 0;
}

int main()
{
    //reading robot
    f>>n;
    robot.resize(n);
    for(i=0;i<n;++i)
        f>>robot[i];
    begin=robot[0];
    for(i=1;i<n;++i)
        begin.x=min(begin.x,robot[i].x),begin.y=min(begin.y,robot[i].y);

    //no-fit-polygon
    f>>m;
    for(i=0;i<m;++i)
    {
        f>>k;
        obstacles[i].resize(k);
        for(j=0;j<k;++j)
            f>>obstacles[i][j];
        obstacles[i]=nfp(robot,obstacles[i]);
    }
    f>>end;

    //graph
    graph.push_back(begin);
    if(begin.not_inside(obstacles,m)==0||end.not_inside(obstacles,m)==0)
    {
        g<<"-1\n";
        return 0;
    }
    graph.push_back(end);
    for(i=0;i<m;++i)
        for(j=0;j<k;++j)
            if(obstacles[i][j].not_inside(obstacles,m))
                graph.push_back(obstacles[i][j]);

    for(i=0;i<(int)graph.size();++i)
        for(j=i+1;j<(int)graph.size();++j)
            if(is_posible(graph[i],graph[j]))
                E[i].push_back(make_pair(j,graph[i].dis(graph[j]))),E[j].push_back(make_pair(i,graph[j].dis(graph[i])));

    //bellman-ford
    Q.push(0);
    for(i=0;i<(int)graph.size();++i)
        been[i]=0,dis[i]=inf;

    dis[0]=0;
    been[0]=1;
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        if(x==1)
            continue;
        been[x]=0;
        for(vector<pair<int,double> >::iterator it=E[x].begin();it!=E[x].end();++it)
            if(dis[x]+it->y<dis[it->x])
            {
                dis[it->x]=it->y+dis[x];
                if(been[it->x]==0)
                    been[it->x]=1,Q.push(it->x);
            }
    }
    g.setf(ios::fixed,ios::floatfield);
    g.precision(2);
    if(cmp(dis[1],inf)==0)
    {
        g<<"-1\n";
        assert(0);
    }
    else
        g<<dis[1]<<"\n";
}