Cod sursa(job #1033134)

Utilizator danalex97Dan H Alexandru danalex97 Data 16 noiembrie 2013 15:02:24
Problema Robot Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.32 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>
using namespace std;

ifstream F("robot.in");
ofstream G("robot.out");

const double eps = 1e-9;
const int infi = 1<<30;
const int debuging = 0;

#define x first
#define y second

typedef pair<int,int> pi;
typedef pair<double,double> pd;

pi finish;
vector<pi> robot;
vector< vector<pi> > obstacle;

int ecu(pi A,pi B,pi C)
{
    int a = A.y - B.y;
    int b = B.x - A.x;
    int c = - A.y * B.x + B.y * A.x;
    int d = a * C.x + b * C.y + c;
    return d > 0 ? 1 : ( d < 0 ? -1 : 0 );
}

int segment(pi A,pi B,pi C)
{
    if ( ecu(A,B,C) ) return 0;
    if ( min(A.x,B.x) > C.x || C.x > max(A.x,B.x) ) return 0;
    if ( min(A.y,B.y) > C.y || C.y > max(A.y,B.y) ) return 0;
    return 1;
}

void print_vector(vector<pi> V)
{
    if ( debuging == 0 ) return;
    G<<"debug: ";
    for (vector<pi>::iterator it=V.begin();it!=V.end();++it)
        G<<'('<<it->x<<","<<it->y<<") ";
    G<<"\n";
}

void cprint_vector(vector<pi> V)
{
    if ( debuging == 0 ) return;
    cout<<"debug: ";
    for (vector<pi>::iterator it=V.begin();it!=V.end();++it)
        cout<<'('<<it->x<<","<<it->y<<") ";
    cout<<"\n";
}

void print_array(double A[],int sz)
{
    if ( debuging == 0 ) return;
    G<<"debug: ";
    for (int i=0;i<sz;++i)
    {
        if ( max(A[i]-infi,infi-A[i]) < eps ) G<<"infi "; else
        G<<fixed<<setprecision(2)<<A[i]<<" ";
    }
    G<<"\n";
}

void read()
{
    int N=0,M=0;
    F>>N;
    for (int i=1,x,y;i<=N;++i)
    {
        F>>x>>y;
        robot.push_back( make_pair(x,y) );
    }
    F>>M;
    for (int i=1;i<=M;++i)
    {
        vector<pi> act;
        F>>N;
        for (int j=1,x,y;j<=N;++j)
        {
            F>>x>>y;
            act.push_back( make_pair(x,y) );
        }
        obstacle.push_back( act );
    }
    F>>finish.x>>finish.y;
}

pi trans(pi a,pi t,pi o)
{
    return make_pair( a.x - o.x + t.x , a.y - o.y + t.y );
}

void convex_hull(vector<pi>& A)
{
    sort(A.begin(),A.end());
    A.erase( unique( A.begin(),A.end() ) , A.end() );
    vector<pi> out;
    vector<pi> stack;
    int N = A.size();

    for (int i=0;i<N;++i)
        if ( ecu(A[0],A[N-1],A[i]) >= 0 )
        {
            if ( stack.size() > 1 )
                while ( ecu( stack[stack.size()-2] , A[i] , stack[stack.size()-1] ) <= 0 )
                {
                    stack.pop_back();
                    if ( stack.size() < 2 ) break;
                }
            stack.push_back(A[i]);
            cprint_vector(stack);
        }
    while ( !stack.empty() )
    {
        stack.pop_back();
        if ( !stack.empty() )
            out.push_back( stack.back() );
    }

    for (int i=N-1;i>=0;--i)
        if ( ecu(A[N-1],A[0],A[i]) >= 0 )
        {
            if ( stack.size() > 1 )
                while ( ecu( stack[stack.size()-2] , A[i] , stack[stack.size()-1] ) <= 0 )
                {
                    stack.pop_back();
                    if ( stack.size() < 2 ) break;
                }
            stack.push_back(A[i]);
            if ( debuging ) cprint_vector(stack);
        }
    while ( !stack.empty() )
    {
        stack.pop_back();
        if ( !stack.empty() )
            out.push_back( stack.back() );
    }

    A = out;
}

void expand()
{
    sort(robot.begin(),robot.end());
    for (size_t i=0;i<obstacle.size();++i)
    {
        int size = obstacle[i].size();
        for (int j=0;j<size;++j)
            for (size_t k=0;k<robot.size();++k)
                obstacle[i].push_back( trans(obstacle[i][j],robot[0],robot[k]) );
        convex_hull( obstacle[i] );
        if ( debuging ) print_vector( obstacle[i] );
    }
}

void placef()
{
    int miny = robot[0].y;
    for (size_t i=1;i<robot.size();++i)
        miny = min(miny,robot[i].y);
    finish.y += robot[0].y-miny;
}

double dist(pi A,pi B)
{
    return sqrt( (A.x-B.x) * (A.x-B.x) + (A.y-B.y) * (A.y-B.y) );
}

int next(int i,int s)
{
    return i+1 < s ? i+1 : 0;
}

int cross(pi a,pi b)
{
    return a.x * b.y - a.y * b.x;
}

int area(vector<pi> v)
{
    int out = 0;
    for (size_t i=0;i<v.size()-1;++i)
        out += cross(v[i],v[i+1]);
    out = max(out,-out);
    return out;
}

int tarea(pi A,pi B,pi C)
{
    int out = cross(A,B) + cross(B,C) + cross(C,A);
    out = max(out,-out);
    return out;
}

int parea(vector<pi> v,pi a)
{
    int out = 0;
    for (size_t i=0;i<v.size()-1;++i)
        out += tarea(v[i],v[i+1],a);
    return out;
}

pd internow;

int int2(pi A,pi B,pi C,pi D)
{
    double a1 = A.y - B.y;
    double b1 = B.x - A.x;
    double c1 = - A.y * B.x + B.y * A.x;

    double a2 = C.y - D.y;
    double b2 = D.x - C.x;
    double c2 = - C.y * D.x + D.y * C.x;

    double d = a1*b2 - b1*a2;
    if ( d == 0 )
        return 0;
    else
    {
        internow = make_pair( (b2*c1-b1*c2)/d , (a1*c2-a2*c1)/d );
        return ecu(C,B,A)*ecu(D,B,A)<=0 && ecu(A,C,D)*ecu(B,C,D)<=0;
    }
}

bool intersection(pi A,pi B,vector<pi> V)
{
    int N = V.size();
    V.push_back(V[0]);

    for (int i=0;i<N;++i)
        if ( ecu(A,V[i],V[i+1]) == 0 && ecu(B,V[i],V[i+1]) == 0 )
            return 0;

    int a=0,b=0;
    for (int i=0;i<N;++i)
    {
        if ( segment(V[i],V[i+1],A) ) a = 1;
        if ( segment(V[i],V[i+1],B) ) b = 1;
    }

    if ( a && b ) return 1;

    int area_v = area(V);
    int area_a = parea(V,A);
    int area_b = parea(V,B);

    if ( area_v == area_a && a == 0 ) return 1;
    if ( area_v == area_b && b == 0 ) return 1;

    vector<pd> inter;
    for (int i=0;i<N;++i)
        if ( int2(A,B,V[i],V[i+1]) )
            inter.push_back( internow );

    //sort(inter.begin(),inter.end());
    //inter.erase(unique(inter.begin(),inter.end()),inter.end());

    return inter.size() > 1;
}

double distancee(pi A,pi B)
{
    if ( A == B ) return 0;
    double out = dist(A,B);
    for (vector< vector<pi> >::iterator vect=obstacle.begin();vect!=obstacle.end();++vect)
        if ( intersection(A,B,*vect) )
            return infi;
    return out;
}

void solve()
{
    vector<pi> points;
    points.push_back( robot[0] );
    for (vector< vector<pi> >::iterator vect=obstacle.begin();vect!=obstacle.end();++vect)
        for (vector<pi>::iterator it=vect->begin();it!=vect->end();++it)
            points.push_back(*it);
    points.push_back( finish );

    int N = points.size();
    double cost[N+10][N+10];
    for (int i=0;i<N;++i)
        for (int j=0;j<N;++j)
            cost[i][j] = distancee(points[i],points[j]);

    for (int i=0;i<N;++i)
        print_array( cost[i],N );

    double d[N+10];
    for (int i=0;i<N;++i)
        d[i] = infi;

    d[0] = 0;
    queue<int> Q;
    Q.push(0);

    if ( debuging ) G<<"\n";

    while ( Q.size() )
    {
        int node = Q.front();
        Q.pop();

        for (int i=0;i<N;++i)
            if ( d[node] + cost[node][i] < d[i] - eps )
            {
                Q.push( i );
                d[i] = d[node] + cost[node][i];
            }
        print_array(d,N);
    }

    G<<fixed<<setprecision(3)<<d[N-1]<<'\n';
}

int main()
{
    read();
    expand();
    placef();
    solve();
}