Cod sursa(job #1488572)

Utilizator retrogradLucian Bicsi retrograd Data 19 septembrie 2015 11:28:13
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.34 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

bool debug = 0;

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

typedef pair<int, int> Point;
#define x first
#define y second

Point start, finish, Robot[14];
int robot_n, obstacles;

void getRobot() {
    fin>>robot_n;

    start = Point(10000, 10000);
    for(int i=1; i<=robot_n; i++) {
        fin>>Robot[i].x>>Robot[i].y;
        start.x = min(start.x, Robot[i].x);
        start.y = min(start.y, Robot[i].y);
    }

    for(int i=1; i<=robot_n; i++) {
        Robot[i].x -= start.x; Robot[i].y -= start.y;
    }
}

vector<Point> UpHull[30], DwHull[30];

int det(Point A, Point B, Point C) {
    int d = (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
    if(d == 0) return 0;
    return d / abs(d);
}

Point Points[5000];
int points;

void MakeHull(int i) {
    sort(Points+1, Points+points+1);

    auto &Up = UpHull[i], &Dw = DwHull[i];

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

        while(Dw.size() >= 2 && det(Dw[Dw.size()-2], Dw[Dw.size()-1], Points[i]) <= 0)
            Dw.pop_back();
        Dw.push_back(Points[i]);
    }

    Up.shrink_to_fit();
    Dw.shrink_to_fit();
}

void dumpP(Point p) {
    cerr<<"("<<p.x<<", "<<p.y<<") ";
}

void getObstacle(int i) {
    int sz, x, y;
    fin>>sz;

    points = 0;
    while(sz--) {
        fin>>x>>y;
        for(int i=1; i<=robot_n; i++)
            Points[++points] = {x - Robot[i].x, y - Robot[i].y};
    }

    MakeHull(i);

    if(debug) {
        auto &Up = UpHull[i], &Dw = DwHull[i];
        cerr<<Up.size() + Dw.size() - 2<<"\n";

        for(auto p : Up) dumpP(p); cerr<<endl;
        for(auto p : Dw) dumpP(p); cerr<<endl;
    }
}

int insidePolygon(Point P, int i) {
    auto &Dw = DwHull[i], &Up = UpHull[i];

    if(P.x <= Dw.front().x || P.x >= Dw.back().x) return false;

    int pos = upper_bound(Up.begin(), Up.end(), P) - Up.begin();
    if(det(Up[pos-1], Up[pos], P) >= 0)
        return false;

    pos = upper_bound(Dw.begin(), Dw.end(), P) - Dw.begin();
    if(det(Dw[pos-1], Dw[pos], P) <= 0)
        return false;

    return true;
}
bool insidePolygons(Point P) {
    for(int i=1; i<=obstacles; i++)
        if(insidePolygon(P, i))
            return true;
    return false;
}


void addAllPoints() {
    points = 0;

    Points[0] = start;

    for(int i=1; i<=obstacles; i++) {
        for(auto p : UpHull[i])
            if(!insidePolygons(p))
                Points[++points] = p;

        for(auto p : DwHull[i])
            if(!insidePolygons(p))
                Points[++points] = p;
    }

    sort(Points+1, Points+points+1);
    points = unique(Points+1, Points+points+1) - Points-1;

    Points[points+1] = finish;

    if(debug) {
        for(int i=0; i<=points+1; i++)
            dumpP(Points[i]);
        cerr<<endl<<endl;
    }
}


bool inter(Point A, Point B, Point C, Point D) {
    if(min(A.x, B.x) > max(C.x, D.x)) return false;
    if(min(A.y, B.y) > max(C.y, D.y)) return false;
    if(max(A.x, B.x) < min(C.x, D.x)) return false;
    if(max(A.y, B.y) < min(C.y, D.y)) return false;

    if(det(A, B, D) == 0)
        return false;

    if(det(A, B, C) * det(A, B, D) <= 0 &&
       det(C, D, A) * det(C, D, B) <= 0) return true;

    return false;
}

int interCount(Point A, Point B, int i) {
    auto &Up = UpHull[i], &Dw = DwHull[i];

    int noi = 0;
    for(int i=1; i<Up.size(); i++)
        if(inter(A, B, Up[i-1], Up[i]))
            noi++;
    for(int i=1; i<Dw.size(); i++)
        if(inter(A, B, Dw[i], Dw[i-1]))
            noi++;

    return noi;
}

bool good(Point A, Point B) {
    for(int i=1; i<=obstacles; i++)
        if(interCount(A, B, i) >= 2)
            return false;
    return true;
}

double C[1005][1005];
void BuildGraph() {
    for(int i=0; i<=points+1; i++)
    for(int j=0; j<i; j++) {
        if(good(Points[j], Points[i])) {
            int dx = Points[i].x - Points[j].x,
                dy = Points[i].y - Points[j].y;
            C[i][j] = C[j][i] = sqrt(dx*dx + dy*dy);

            if(debug) {
                cerr<<i<<" <-> "<<j<<'\n';
            }

        } else {
            C[i][j] = C[j][i] = 1e17;
        }
    }
}


double D[10000];
bool Viz[10000];

double Dijkstra() {
    for(int i=1; i<=points+1; i++)
        D[i] = 1e17;

    while(true) {
        int choose = points+1;
        for(int i=0; i<=points; i++)
            if(!Viz[i] && D[choose] > D[i])
                choose = i;

        if(choose == points+1 || D[choose] >= 5e16)
            return D[choose];
        Viz[choose] = 1;

        for(int i=1; i<=points+1; i++) {
            D[i] = min(D[i], D[choose] + C[choose][i]);
        }

    }

    return -1;
}

int main() {
    getRobot();

    fin>>obstacles;
    for(int i=1; i<=obstacles; i++)
        getObstacle(i);

    fin>>finish.x>>finish.y;

    if(insidePolygons(finish)) {
        fout<<-1;
        return 0;
    }

    addAllPoints();
    BuildGraph();
    double d = Dijkstra();

    if(d >= 5e16) fout<<-1;
    else fout<<fixed<<setprecision(4)<<d;

}