Cod sursa(job #1282306)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 4 decembrie 2014 00:52:28
Problema Robot Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.42 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <cmath>
#include <utility>
#include <bitset>

#define eps 0.00000001
#define inf 50012500000005.0
using namespace std;

struct point{
    double x,y;

    point(double x=0,double y=0): x(x), y(y) {}
};

bool operator!=(const point &a,const point &b){
    return (fabs(a.x-b.x)>=eps || fabs(a.y-b.y)>=eps);
}

double ccw(const point &a,const point &b,const point &c){
    return (((a.x-b.x)*(c.y-b.y))-((a.y-b.y)*(c.x-b.x)));
}

point reference;
bool operator<(const point &a,const point &b){
    if(fabs(ccw(a,reference,b))<eps)
        return a.x<b.x;
    return ccw(a,reference,b)>-eps;
}

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

vector<point> robot;
point corner;

vector<point> obstacles[30];

vector<point> convex_hull(vector<point> points){
    if(points.size()<3)
        return points;

    int i;

    int pos=0;
    for(i=1;i<points.size();i++)
        if(points[i].x<points[pos].x || (points[i].x==points[pos].x && points[i].y<points[pos].y))
            pos=i;

    swap(points[0],points[pos]);

    reference=points[0];

    sort(points.begin()+1,points.end());

    vector<point> stack;
    stack.push_back(points[0]);
    stack.push_back(points[1]);

    for(i=2;i<points.size();i++){
        while(stack.size()>1 && ccw(stack[stack.size()-2],stack.back(),points[i])>-eps)
            stack.pop_back();

        stack.push_back(points[i]);
    }


    return stack;
}

bool intersects(const point a,const point b,const point c,const point d){
    if((a.y-b.y)*(c.x-d.x)==(c.y-d.y)*(a.x-b.x))
        return false;

    point p;
    if(fabs(a.x-b.x)<eps){
        double m2=(c.y-d.y)/(c.x-d.x);
        double n2=d.y-m2*d.x;

        p.x=a.x;
        p.y=m2*p.x+n2;
    }
    else if(fabs(c.x-d.x)<eps){
        double m1=(a.y-b.y)/(a.x-b.x);
        double n1=b.y-m1*b.x;

        p.x=c.x;
        p.y=m1*p.x+n1;
    }
    else{
        double m1=(a.y-b.y)/(a.x-b.x);
        double m2=(c.y-d.y)/(c.x-d.x);
        double n1=b.y-m1*b.x;
        double n2=d.y-m2*d.x;

        p.x=(n2-n1)/(m1-m2);
        p.y=m1*p.x+n1;
    }

    return (p!=a && p!=b && p!=c && p!=d && min(a.x,b.x)-eps<=p.x && p.x<=max(a.x,b.x)+eps && min(c.x,d.x)-eps<=p.x && p.x<=max(c.x,d.x)+eps && min(a.y,b.y)-eps<=p.y && p.y<=max(a.y,b.y)+eps && min(c.y,d.y)-eps<=p.y && p.y<=max(c.y,d.y)+eps);
}

inline void compute_corner(){
    corner=robot[0];
    for(int i=1;i<robot.size();i++){
        if(robot[i].x<corner.x)
            corner.x=robot[i].x;
        if(robot[i].y<corner.y)
            corner.y=robot[i].y;
    }
}

vector<point> shrinked_polygon(vector<point> points){
    vector<point> ans;

    int i,j;
    for(i=0;i<points.size();i++)
        for(j=0;j<robot.size();j++)
            ans.push_back(point(points[i].x-(robot[j].x-corner.x),points[i].y-(robot[j].y-corner.y)));

    return convex_hull(ans);
}

int m;
vector<point> shrinked_obstacles[30];

inline void compute_shrinked_obstacles(){
    for(int i=1;i<=m;i++){
        shrinked_obstacles[i]=shrinked_polygon(obstacles[i]);
    }
}

bool intersects(const point &a,const point &b){
    int i,j;
    for(i=1;i<=m;i++){
        if(shrinked_obstacles[i].size()<2)
            continue;

        for(j=0;j<shrinked_obstacles[i].size()-1;j++){
            if(intersects(a,b,shrinked_obstacles[i][j],shrinked_obstacles[i][j+1])){
                return true;
            }
        }

        if(intersects(a,b,shrinked_obstacles[i][shrinked_obstacles[i].size()-1],shrinked_obstacles[i][0])){
            return true;
        }

        if(shrinked_obstacles[i].size()==2)
            continue;

        for(j=0;j<shrinked_obstacles[i].size()-2;j++){
            if(intersects(a,b,shrinked_obstacles[i][j],shrinked_obstacles[i][j+2])){
                return true;
            }
        }

        if(intersects(a,b,shrinked_obstacles[i][shrinked_obstacles[i].size()-2],shrinked_obstacles[i][0])){
            return true;
        }

        if(intersects(a,b,shrinked_obstacles[i][shrinked_obstacles[i].size()-1],shrinked_obstacles[i][1])){
            return true;
        }
    }

    return false;
}

int n;
point destination;
vector<point> all_final_points;

inline void compute_all_final_points(){
    int i,j;

    all_final_points.push_back(corner);
    for(i=1;i<=m;i++)
        for(j=0;j<shrinked_obstacles[i].size();j++)
            all_final_points.push_back(shrinked_obstacles[i][j]);
    all_final_points.push_back(destination);

    n=all_final_points.size();
}

double d[5005];
priority_queue<pair<double,int> > coada;
bitset<5005> viz;

inline double compute_shortest_path(){
    int i;
    for(i=1;i<n;i++)
        d[i]=inf;

    coada.push(make_pair(-dist(all_final_points[0],all_final_points[n-1]),0));

    pair<double,int> y;

    while(!coada.empty()){
        y=coada.top();
        coada.pop();

        if(y.second==(n-1))
            break;

        if(!viz[y.second]){
            viz[y.second]=1;

            for(i=1;i<n;i++)
                if(!intersects(all_final_points[y.second],all_final_points[i]) && d[y.second]+dist(all_final_points[y.second],all_final_points[i])<d[i]){
                    d[i]=d[y.second]+dist(all_final_points[y.second],all_final_points[i]);
                    coada.push(make_pair(-d[i]-dist(all_final_points[i],all_final_points[n-1]),i));
                }
        }
    }

    if(d[n-1]!=inf)
        return d[n-1];
    else
        return (-10);
}

ifstream cin("robot.in");
inline void read(){
    int n=0,i,j;
    cin>>n;

    robot.resize(n);
    for(i=0;i<n;i++)
        cin>>robot[i].x>>robot[i].y;

    int p=0;

    cin>>m;

    for(i=1;i<=m;i++){
        cin>>p;
        obstacles[i].resize(p);

        for(j=0;j<p;j++)
            cin>>obstacles[i][j].x>>obstacles[i][j].y;
    }

    cin>>destination.x>>destination.y;
}

inline void prepare(){
    compute_corner();
    compute_shrinked_obstacles();
    compute_all_final_points();
}

int main()
{
    ofstream cout("robot.out");

    read();
    prepare();

    double ans=compute_shortest_path();
    if(ans<0)
        cout<<"-1\n";
    else
        cout<<fixed<<setprecision(6)<<ans<<'\n';

    cin.close();
    cout.close();
    return 0;
}