Cod sursa(job #1256599)

Utilizator MirceaTrRaduta Mircea MirceaTr Data 6 noiembrie 2014 17:02:55
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.69 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)
{
    int d =  det (firstpoint,a,b);

    if (d == 0)
    {
        return a.x < b.x;
    }
    return d > 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)
    {
        if (!st.empty () && poly[i] == st[st.size()-1])
          continue;

        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]);
    }
}

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]);
}

double dist (const point &a, const point &b)
{
    return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

bool intersection1 (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);
}

int point_in_polygon (const point &a, const vector<point> &poly)
{
    int s = poly.size(), which = -2;

    for (int i=0; i<s; ++i)
    {
        int d = det (poly[i],poly[(i+1)%s],a);

        if (d != 0)
        {
            if (which == -2)
              which = d/abs(d);
            else if (which != d/abs(d))
              which = 0;
        }
        else
        {
            if (dist (poly[i],a) <= dist(poly[i],poly[(i+1)%s]) && dist(poly[(i+1)%s],a) <= dist(poly[i],poly[(i+1)%s]))
                 return 0;
        }
    }

    if (which != 0)
      return 1;
    return -1;
}

bool segment_polygon_intersection (const point &a, const point &b, const vector<point> &poly)
{
    int s = poly.size (), which = -2;

    for (int i=0; i<s; ++i)
    {
        int d = det (a,b,poly[i]);

        if (d != 0)
        {
            if (which == -2)
                which = d/abs(d);
            else if (which != d/abs(d))
                which = 0;
        }
    }

    if (which != 0)
      return 0;  //coresponding line doesn't cross polygon

    int ok1 = point_in_polygon (a,poly);
    int ok2 = point_in_polygon (b,poly);

    if (ok1 == 0 && ok2 == 0 || ok1 == 1 ||  ok2 == 1)
       return 1; // segment starts/ends or starts and ends within the polygon

    int cnt = 0;

    for (int i=0; i<s; ++i)
    {
        if (intersection1(a,b,poly[i],poly[(i+1)%s]))
          return 1; // segment cuts a line directly
        cnt += intersection2(a,b,poly[i],poly[(i+1)%s]);
    }

    if (cnt >= 4)
      return 1; //segment enters and exits the polygon through points of the polgon, sneaky segment

    return 0;
}

bool adj (int i, int j)
{
    for (int k=1; k<=m;  ++k)
       if (segment_polygon_intersection (graph[i],graph[j],newob[k]))
        return 0;

    return 1;
}

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

    H.push (make_pair(dist(graph[0],graph[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))
           {
               double dst = dist (graph[x],graph[i]);

               if (d[x] + dst < d[i])
               {
                   d[i] = d[x] + dst;
                   H.push (make_pair (d[i] + dist (graph[i],graph[1]),i));
               }
           }
       }
    }
}

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

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