Cod sursa(job #1277359)

Utilizator lokixdSebastian lokixd Data 27 noiembrie 2014 16:25:24
Problema Robot Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.74 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];
}