Cod sursa(job #1010496)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 15 octombrie 2013 00:14:26
Problema Robot Scor 25
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.83 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <cmath>

#define PM 2600
#define INF 1e9
#define EPS 1e-8
#define x first
#define y second

using namespace std;

ifstream f("robot.in");
ofstream g("robot.out");

typedef pair<int, int> PI;
typedef pair<double, double> PD;

PD intersection;
PI Finish;
vector<PI> Robot;
vector< vector<PI> > Obstacles;

inline bool Equal (double x, double y)
{
    return fabs(x-y)<EPS;
}

inline int Sign (PD P1, PD P2, PD P3)
{
    double S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
    if (Equal(S, 0.0)) return 0;
    return (S<0?-1:1);
}

inline int Area (PI P1, PI P2, PI P3)
{
    int S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
    return (S<0?-S:S);
}

inline bool onSegment (PI A, PI B, PI P)
{
    if (Sign(A, B, P)!=0) return 0;
    if (min(A.x, B.x)>P.x || P.x>max(A.x, B.x)) return 0;
    if (min(A.y, B.y)>P.y || P.y>max(A.y, B.y)) return 0;
    return 1;
}

inline int Polygon_Area (vector<PI>& V)
{
    int i, ANS=0;

    for (i=0; i<(int)V.size(); i++)
        ANS+=V[i].x*V[(i+1<(int)V.size()?i+1:0)].y-V[i].x*V[(i>0?i-1:V.size()-1)].y;

    return (ANS<0?-ANS:ANS);
}

inline int PInside_Area (PI P, vector<PI>& V)
{
    int i, ANS=0;

    for (i=0; i<(int)V.size(); i++)
        ANS+=Area(V[i], V[(i+1<(int)V.size()?i+1:0)], P);

    return ANS;
}

void Convex_Hull (vector<PI>& V)
{
    sort(V.begin(), V.end());
    V.resize(unique(V.begin(), V.end()) - V.begin());

    vector<PI> ST;

    int K=1, i;
    ST.push_back(V[0]);

    for (i=1; i<(int)V.size(); i++)
    {
        while (K>1 && Sign(ST[K-2], ST[K-1], V[i]))
        {
            ST.pop_back();
            K--;
        }

        ST.push_back(V[i]);
        K++;
    }

    V.clear();
    V.push_back(ST[ST.size()-1]);
    for (i=0; i<(int)ST.size()-1; i++)
        V.push_back(ST[i]);
}

bool IntersectSegment (PI A, PI B, PI C, PI D)
{
    double a, b, c, a2, b2, c2, m;

    a=B.y-A.y;
    b=A.x-B.x;
    c=a*A.x + b*A.y;

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

    m=a*b2 - b*a2;
    if (m==0) return 0;

    intersection=make_pair((b2*c-b*c2)/m, (a*c2-a2*c)/m);

    return (Sign(C, B, A)*Sign(D, B, A)<=0 && Sign(A, C, D)*Sign(B, C, D)<=0);
}

bool IntersectPolygon (PI A, PI B, vector<PI>& V)
{
    for (int i=0; i<(int)V.size(); i++)
        if (Sign(A, V[i], V[(i+1<(int)V.size()?i+1:0)])==0 && Sign(B, V[i], V[(i+1<(int)V.size()?i+1:0)])==0)
            return 0;

    bool OnPolygonA=0, OnPolygonB=0;

    for (int i=0; i<(int)V.size(); i++)
    {
        int nx=(i+1<(int)V.size()?i+1:0);
        OnPolygonA|=onSegment(V[i], V[nx], A);
        OnPolygonB|=onSegment(V[i], V[nx], B);
    }

    if (OnPolygonA && OnPolygonB)
        return 1;

    int AreaP=Polygon_Area(V);
    int AreaA=PInside_Area(A, V), AreaB=PInside_Area(B, V);

    if ((AreaP==AreaA && OnPolygonA==0) || (AreaP==AreaB && OnPolygonB==0))
        return 1;

    vector<PD> IntersectionP;
    for (int i=0; i<(int)V.size(); i++)
        if (IntersectSegment(A, B, V[i], V[(i+1<(int)V.size()?i+1:0)]))
            IntersectionP.push_back(intersection);

    sort(IntersectionP.begin(), IntersectionP.end());
    IntersectionP.resize(unique(IntersectionP.begin(), IntersectionP.end()) - IntersectionP.begin());

    return IntersectionP.size()>=2;
}

void Expand_Obstacles ()
{
    sort(Robot.begin(), Robot.end());

    for (int i=0; i<(int)Obstacles.size(); i++)
    {
        int size=Obstacles[i].size();

        for (int j=0; j<size; j++)
            for (int k=0; k<(int)Robot.size(); k++)
                Obstacles[i].push_back(make_pair(Obstacles[i][j].x+Robot[0].x-Robot[k].x, Obstacles[i][j].y+Robot[0].y-Robot[k].y));

        Convex_Hull(Obstacles[i]);
    }
}

void Calculate_Finish ()
{
    int miny=Robot[0].y;
    for (int i=1; i<(int)Robot.size(); i++)
        miny=min(miny, Robot[i].y);
    Finish.y+=Robot[0].y-miny;
}

double GetDist (PI A, PI B)
{
    if (A==B) return 0;
    double ANS=sqrt(1.0*(A.x-B.x)*(A.x-B.x) + 1.0*(A.y-B.y)*(A.y-B.y));

    for (int i=0; i<(int)Obstacles.size(); i++)
        if (IntersectPolygon(A, B, Obstacles[i]))
            return INF;

    return ANS;
}

double Solve ()
{
    vector<PI> points;
    points.push_back(Robot[0]);

    for (int i=0; i<(int)Obstacles.size(); i++)
        for (int j=0; j<(int)Obstacles[i].size(); j++)
            points.push_back(Obstacles[i][j]);
    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]=GetDist(points[i], points[j]);

    double Dist[N+10];
    for (int i=0; i<N; i++)
        Dist[i]=INF;

    Dist[0]=0;
    queue<int> Q;
    Q.push(0);
    int node, i;

    while (!Q.empty())
    {
        node=Q.front();
        Q.pop();

        for (i=0; i<N; i++)
            if (Dist[node]+Cost[node][i]<=Dist[i]-EPS)
            {
                Q.push(i);
                Dist[i]=Dist[node]+Cost[node][i];
            }
    }

    return Dist[N-1];
}

int main ()
{
    int N;
    f >> N;
    for (int i=1; i<=N; i++)
    {
        int a, b;
        f >> a >> b;
        Robot.push_back(make_pair(a, b));
    }

    int M;
    f >> M;
    for (int i=1; i<=M; i++)
    {
        vector<PI> Aux;
        f >> N;
        for (int j=1; j<=N; j++)
        {
            int a, b;
            f >> a >> b;
            Aux.push_back(make_pair(a, b));
        }

        Obstacles.push_back(Aux);
    }

    f >> Finish.x >> Finish.y;

    Expand_Obstacles();
    Calculate_Finish();

    g << Solve() << '\n';

    f.close();
    g.close();

    return 0;
}