Cod sursa(job #1821540)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 3 decembrie 2016 12:09:23
Problema Robot Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.21 kb
//cateva biblioteci
#include <cstdio>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>

//"e adevaraciune"
#define adevaratadevarat true

//pair, exploatat ca punct
#define punct std::pair <int, int>
#define x first
#define y second

//"dimensiunea sistemului"
#define INF 1000000000
#define EPS 0.00000001

//limitele impuse de #comisie
#define MAXN 10
#define MAXM 25
#define MAXU 250
#define MAXK 510
#define MASK 511

//asta inseamna sa fii muchie
struct muchie{
    int x;
    double y;
    muchie(int _x, double _y){
        x=_x;
        y=_y;
    }
};

//iata poligoanele
punct r[MAXN], o[MAXM][MAXU+MAXN], a[MAXK];
int u[MAXM], h[MASK+1];
bool viz[MAXK];

//pentru distante
std::vector <muchie> v[MAXK];
double d[MAXK];

//ce facem cand nu mai avem ce face? modulam!
inline int myabs(int a){
    if(a<0) return -a;
    else return a;
}

//Urgent! Aria!
inline int arie(punct a, punct b, punct c){
    return a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
}

//doar distanta o vrem
inline double dist(punct a, punct b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

//verificam daca segementele (A-B) si [P-Q] se intersecteaza intr-un singur punct
inline bool intersect(punct a, punct b, punct p, punct q){
    if((a==p)||(a==q)||(b==p)||(b==q)) return 0;
    if(std::max(std::min(a.x, b.x), std::min(p.x, q.x))>std::min(std::max(a.x, b.x), std::max(p.x, q.x))) return 0;
    if(std::max(std::min(a.y, b.y), std::min(p.y, q.y))>std::min(std::max(a.y, b.y), std::max(p.y, q.y))) return 0;
    long long s1=arie(a, b, p), s2=arie(a, b, q), s3=arie(p, q, a), s4=arie(p, q, b);
    return ((((s1<0)&&(s2>0))||((s1>0)&&(s2<0)))&&(((s3<0)&&(s4>0))||((s3>0)&&(s4<0))));
}

//Se afla Q pe linia (A-B)?
inline bool peLinie(punct q, punct a, punct b){
    return (std::fabs(dist(a, b)-dist(a, q)-dist(q, b))<EPS);
}

//Belciug iti da pozitia lui Ion, proprietatea lui Herdelea
//si te intreaba unde e Hector
inline bool punctInPoligon(punct Ion, punct v[], int n){
    for(int i=0; i<n; i++)
        if(Ion==v[i])
            return 0;
    if(peLinie(Ion, v[n-1], v[0])) return 0;
    for(int i=1; i<n; i++)
        if(peLinie(Ion, v[i-1], v[i]))
            return 0;

    int arie1=0, arie2=myabs(arie(Ion, v[n-1], v[0]));
    for(int i=1; i<n; i++)
        arie2+=myabs(arie(Ion, v[i-1], v[i]));
    for(int i=2; i<n; i++)
        arie1+=arie(v[0], v[i-1], v[i]);
    return (arie1==arie2);
}

//ne punem intrebarea: linia de la A la B trece prin vreun obstacol?
inline bool corect(punct a, punct b, int m){
    for(int i=0; i<m; i++){
        if(punctInPoligon(a, o[i], u[i])) return 0;
        if(punctInPoligon(b, o[i], u[i])) return 0;
        for(int j=0; j<u[i]; j++)
            for(int p=j+1; p<u[i]; p++)
                if(intersect(a, b, o[i][j], o[i][p]))
                    return 0;
    }
    return adevaratadevarat;
}

//vom scoate si punctele coliniare
inline void convexHull(punct v[], int n, punct st[], int &vf){
    std::sort(v, v+n);
    vf=1;
    st[0]=v[0];
    for(int i=1; i<n; i++){
        if(arie(v[0], v[i], v[n-1])>=0){
            while((vf>1)&&(arie(st[vf-2], st[vf-1], v[i])<=0))
                vf--;
            st[vf++]=v[i];
        }
    }
    for(int i=n-1; i>0; i--){
        if(arie(v[0], v[i], v[n-1])<0){
            while((vf>1)&&(arie(st[vf-2], st[vf-1], v[i])<=0))
                vf--;
            st[vf++]=v[i];
        }
    }
    while((vf>1)&&(arie(st[vf-2], st[vf-1], v[0])<=0))
        vf--;
}

//acum e acum!
inline void extind(punct a[], int &t, int n, punct q){
    //luam fiecare punct al obstacolului
    //si fiecare punct al robotului
    //si retinem in sol[] punctul de referinta al robotului
    //obtinut pentru pozitia respectiva
    punct sol[MAXK];
    int k=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<t; j++){
            sol[k].x=q.x+a[j].x-r[i].x;
            sol[k].y=q.y+a[j].y-r[i].y;
            k++;
        }
    }

    //obstacolul extins este infasuratoarea convexa
    //a punctelor din sol[]
    convexHull(sol, k, a, t);
}

//take courage, men!
int main(){
    FILE *fin, *fout;
    fin=fopen("robot.in", "r");
    fout=fopen("robot.out", "w");

    //gasim robotul
    int n;
    fscanf(fin, "%d", &n);
    for(int i=0; i<n; i++)
        fscanf(fin, "%d%d", &r[i].x, &r[i].y);

    //gasim obstacolele
    int m;
    fscanf(fin, "%d", &m);
    for(int i=0; i<m; i++){
        fscanf(fin, "%d", &u[i]);
        for(int j=0; j<u[i]; j++)
            fscanf(fin, "%d%d", &o[i][j].x, &o[i][j].y);
    }

    //aflam coordonatele punctului destinatie
    punct f;
    fscanf(fin, "%d%d", &f.x, &f.y);

    //aflam punctul de reper al robotului
    punct q=r[0];
    for(int i=1; i<n; i++){
        if(r[i].x<q.x) q.x=r[i].x;
        if(r[i].y<q.y) q.y=r[i].y;
    }

    //ca sa aducem robotul la forma unui punct
    //extindem obstacolele
    for(int i=0; i<m; i++)
        extind(o[i], u[i], n, q);

    //colectam punctele
    a[0]=q;
    a[1]=f;
    int k=2;
    for(int i=0; i<m; i++)
        for(int j=0; j<u[i]; j++)
            a[k++]=o[i][j];

    //ducem muchii intre puncte
    for(int i=0; i<k; i++){
        for(int j=i+1; j<k; j++){
            if(corect(a[i], a[j], m)){
                v[i].push_back(muchie(j, dist(a[i], a[j])));
                v[j].push_back(muchie(i, dist(a[i], a[j])));
            }
        }
    }

    //calculam distanta dintre nodul 0 si nodul 1
    //folosind algoritmul Bellman-Ford
    for(int i=1; i<k; i++)
        d[i]=INF;
    int st=0, dr=0;
    h[dr++]=0;
    viz[0]=1;
    while(st<dr){
        int x=h[st&MASK];
        viz[x]=0;
        st++;
        for(auto y:v[x]){
            if(d[x]+y.y<d[y.x]){
                d[y.x]=d[x]+y.y;
                if(!viz[y.x]){
                    viz[y.x]=1;
                    h[dr&MASK]=y.x;
                    dr++;
                }
            }
        }
    }

    //afisam distanta minima obtinuta sau -1 in caz ca nu am gasit niciun drum
    if(d[1]>INF/2) fprintf(fout, "-1\n");
    else fprintf(fout, "%.2f\n", d[1]);

    //gata!
    fclose(fin);
    fclose(fout);
    return 0;
}