Cod sursa(job #1216621)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 5 august 2014 07:18:25
Problema Robot Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.13 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define inf 100000001
#define point pair<int,int>
#define x first
#define y second
#define eps 1e-9

using namespace std;

ifstream fin ("robot.in");
ofstream fout ("robot.out");

vector<point> robot,ob[26],newob[26],st,graph;
point pivot,firstpoint,start,dest;
bool viz[2501];
double d[2501];
int m;
priority_queue <pair<double,int>, vector<pair<double,int> >, greater<pair<double,int> > >H;

void read (vector<point> &poly)
{
    int n,x,y;
    fin>>n;

    for (int i=0; i<n; ++i)
    {
        fin>>x>>y;
        poly.push_back (make_pair(x,y));
    }
}

void read ()
{
    read (robot);

    int minx = inf, miny = inf;

    for (int i=0; i<robot.size(); ++i)
    {
        minx = min (minx,robot[i].x);
        miny = min (miny,robot[i].y);
    }

    pivot = make_pair (minx,miny);

    fin>>m;

    for (int i=1; i<=m; ++i)
       read (ob[i]);

    fin>>dest.x>>dest.y;
}

int det (const point &a, const point &b, const point &c)
{
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

bool cmp (const point &a, const point &b)
{
    return det (firstpoint,a,b) > 0;
}

void convex_hull (vector<point> &poly)
{
    int minp=0;

    for (int i=0; i<poly.size(); ++i)
    {
        if (poly[i] < poly[minp])
          minp = i;
    }

    swap (poly[minp],poly[0]);
    vector<point>::iterator it = poly.begin();
    ++it;
    firstpoint = poly[0];
    sort (it,poly.end(),cmp);

    st.clear();

    for (int i=0; i<poly.size(); ++i)
    {
        while (st.size() >= 2 && det (st[st.size()-2],st[st.size()-1],poly[i]) <= 0)
           st.pop_back ();
        st.push_back(poly[i]);
    }

    poly = st;
}

void get_newob ()
{
    for (int i=1; i<=m; ++i)
    {
        for (int j=0; j<ob[i].size(); ++j)
            for (int k=0; k<robot.size(); ++k)
                newob[i].push_back (make_pair(pivot.x + ob[i][j].x - robot[k].x,pivot.y + ob[i][j].y - robot[k].y));

        convex_hull (newob[i]);
    }
}

bool intersection (const point &A1, const point &A2, const point &B1, const point &B2)
{
    return (1LL*det(A1,A2,B1)*det(A1,A2,B2) < 0 && 1LL*det(B1,B2,A1)*det(B1,B2,A2) < 0);
}

bool intersection2 (const point &A1, const point &A2, const point &B1, const point &B2)
{
    return (1LL*det(A1,A2,B1)*det(A1,A2,B2) == 0 || 1LL*det(B1,B2,A1)*det(B1,B2,A2) == 0);
}

void build_graph()
{
    start = pivot;
    graph.push_back (start);
    graph.push_back (dest);

    for (int i=1; i<=m; ++i)
        for (int j=0; j<newob[i].size(); ++j)
          graph.push_back (newob[i][j]);
}

bool adj (int i, int j)
{
    bool ok = 1;

    for (int k=1; k<=m; ++k)
    {
        int cnt = 0;
        for (int h=0; h<newob[k].size(); ++h)
        {
            ok &= !intersection (graph[i],graph[j],newob[k][h],newob[k][(h==newob[k].size()-1)?0:h+1]);
            cnt = cnt + intersection2 (graph[i],graph[j],newob[k][h],newob[k][(h==newob[k].size()-1)?0:h+1]);
        }

        if (cnt >= 4)
          return 0;
    }

    return ok;
}

double dist (int i, int j)
{
    return sqrt ((graph[i].x-graph[j].x)*(graph[i].x-graph[j].x) + (graph[i].y-graph[j].y)*(graph[i].y-graph[j].y));
}

void dijkstra ()
{
    for (int i=1; i<graph.size(); ++i)
       d[i] = inf;

    H.push (make_pair(dist(0,1),0));

    while (!H.empty())
    {
        int x = H.top().second;
        H.pop ();

        if (viz[x])
          continue;

        viz[x] = 1;
        if (x == 1)
          break;

       for (int i=0; i<graph.size(); ++i)
       {
           if (adj(x,i))
           {
               if (d[x] + dist(x,i) < d[i])
               {
                   d[i] = d[x] + dist(x,i);
                   H.push (make_pair (d[i] + dist (i,1),i));
               }
           }
       }
    }
}

int main()
{
    read ();
    get_newob ();
    build_graph ();
    dijkstra ();

    if (fabs(d[1]-inf) < eps)
      fout<<-1;
    else fout<<fixed<<setprecision(4)<<d[1];
}