Cod sursa(job #987686)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 21 august 2013 12:32:03
Problema Robot Scor 55
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.78 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;
 
#define NMAX 3001
#define MMAX 26
#define pb push_back
#define mp make_pair
#define Punct pair < int , int >
#define Punctd pair < double , double >
#define sz(a) ((a).size())
#define INF 1<<30
 
vector <Punct> robot,st;
vector <Punct> obstacol[MMAX];
Punct H;
Punctd P;
int viz[NMAX],m;
double c[NMAX][NMAX],d[NMAX];
 
inline int cross_product(Punct A, Punct B, Punct C)
{
    return (B.first-A.first)*(C.second-A.second)-(C.first-A.first)*(B.second-A.second);
}
 
inline double dist(Punct A, Punct B)
{
    return (double)sqrt((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second));
}
 
struct cmp {
    bool operator () (const Punct &A, const Punct &B) {
        return cross_product(H,A,B)>0;
    }
};
 
void Graham_scan(vector <Punct> &v)
{
    int i,lim,nr;
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    lim=sz(v);
    H=*(v.begin());
    sort(v.begin()+1,v.end(),cmp());
    st.clear();
    st.pb(v[0]);
    st.pb(v[1]);
    nr=1;
    for(i=2;i<=lim-1;i++) {
        while(nr>=1 && cross_product(st[nr-1],st[nr],v[i])<=0) {
            nr--;
            st.pop_back();
        }
        nr++;
        st.pb(v[i]);
    }
    st.pb(st[0]);
    v=st;
}
 
void make_NFP(vector <Punct> &v)
{
    int i,lim;
    lim=sz(v);
    for(i=0;i<=lim-1;i++)
        for(vector <Punct> :: iterator it=robot.begin();it!=robot.end();it++)
            v.pb(mp(robot[0].first+v[i].first-(it->first),robot[0].second+v[i].second-(it->second)));
    Graham_scan(v);
}
 
void make_finish(int &x, int &y)
{
    int miny,i,n;
    miny=INF;
    n=sz(robot)-1;
    for(i=0;i<=n;i++)
        if(robot[i].second<miny)
            miny=robot[i].second;
    y=y+robot[0].second-miny;
}
 
inline int interior(Punct A, Punct B, Punct C)
{
    if(cross_product(A,B,C)!=0)
        return 0;
    if(min(B.first,C.first)<=A.first && A.first<=max(B.first,C.first) && min(B.second,C.second)<=A.second && A.second<=max(B.second,C.second))
        return 1;
    return 0;
}
 
inline int contur(Punct A, vector <Punct> v)
{
    int i,lim;
    lim=sz(v)-1;
    for(i=0;i<=lim-1;i++)
        if(interior(A,v[i],v[i+1]))
            return 1;
    return 0;
}
int arie_poligon(vector <Punct> v)
{
    int sol,i,lim;
    sol=0;
    lim=sz(v)-1;
    for(i=0;i<=lim-1;i++)
        sol=sol+v[i].first*v[i+1].second - v[i+1].first*v[i].second;
    return abs(sol);
}
 
inline int intersecteaza(Punct A, Punct B, Punct C, Punct D)
{
    int a,b,c,a2,b2,c2,det;
    a=B.second-A.second;
    b=A.first-B.first;
    c=A.second*B.first-A.first*B.second;
    a2=D.second-C.second;
    b2=C.first-D.first;
    c2=C.second*D.first-C.first*D.second;
     
    det=a*b2-b*a2;
    if(det==0)
        return 0;
    P=mp((double)(b*c2-c*b2)/det,(double)(a2*c-a*c2)/det);
    return (cross_product(A,B,C)*cross_product(A,B,D)<=0 && cross_product(C,D,A)*cross_product(C,D,B)<=0);
}
 
inline int interior_poligon(Punct A, vector <Punct> v)
{
    int i,lim,arie;
    vector <Punct> aux;
    lim=sz(v)-1;
    arie=0;
    for(i=0;i<=lim-1;i++) {
        aux.clear();
        aux.pb(v[i]);
        aux.pb(v[i+1]);
        aux.pb(A);
        aux.pb(v[i]);
        arie=arie+arie_poligon(aux);
    }
    if(arie==arie_poligon(v))
        return 1;
    return 0;
}
 
inline int visible(Punct A, Punct B, vector <Punct> v)
{
    int i,lim,c1,c2;
    lim=sz(v)-1;
    for(i=0;i<=lim-1;i++)
        if(cross_product(v[i],v[i+1],A)==0 && cross_product(v[i],v[i+1],B)==0)
            return 1;
    c1=contur(A,v);
    c2=contur(B,v);
    if(c1 && c2)
        return 0;
    if(interior_poligon(A,v) && c1==0) 
        return 0;
    if(interior_poligon(B,v) && c2==0)
        return 0;
    vector <Punctd> aux;
    for(i=0;i<=lim-1;i++)
        if(intersecteaza(A,B,v[i],v[i+1])) 
            aux.pb(P);
    sort(aux.begin(),aux.end());
    aux.resize(unique(aux.begin(),aux.end())-aux.begin());
    return sz(aux)<=1;
}
 
double distanta(Punct A, Punct B)
{
    int i;
    if(A==B)
        return 0;
    for(i=1;i<=m;i++)
        if(visible(A,B,obstacol[i])==0)
            return INF;
    return dist(A,B);
}
 
double dijkstra(int n)
{
    int i,nod;
    double minim;
    for(i=1;i<=n;i++)
        d[i]=INF;
    while(viz[n]==0) {
        minim=INF;
        for(i=0;i<=n;i++)
            if(viz[i]==0 && d[i]<minim) {
                minim=d[i];
                nod=i;
            }
        if(minim==INF)
            return INF;
        viz[nod]=1;
        for(i=0;i<=n;i++)
            d[i]=min(d[i],minim+c[nod][i]);
    }
    return d[n];
}
 
int main ()
{
    int n,i,j,x,y,p,lim;
    double sol;
    ifstream f("robot.in");
    ofstream g("robot.out");
    f>>n;
    for(i=1;i<=n;i++) {
        f>>x>>y;
        robot.pb(mp(x,y));
    }
    f>>m;
    for(i=1;i<=m;i++) {
        f>>p;
        for(j=1;j<=p;j++) {
            f>>x>>y;
            obstacol[i].pb(mp(x,y));
        }
    }
    f>>x>>y;
    f.close();
    sort(robot.begin(),robot.end());
    for(i=1;i<=m;i++)
        make_NFP(obstacol[i]);
	make_finish(x,y);
    vector <Punct> v;
    v.pb(robot[0]);
    for(i=1;i<=m;i++) {
        lim=sz(obstacol[i])-1;
        for(j=0;j<=lim-1;j++)
            v.pb(obstacol[i][j]);
    }
    v.pb(mp(x,y));
    lim=sz(v)-1;
    for(i=0;i<=lim;i++)
        for(j=0;j<=lim;j++) {
            if(i==j)
                continue;
            c[i][j]=distanta(v[i],v[j]);
        }
    sol=dijkstra(lim);
    if(sol==INF)
        g<<"-1";
    else {
        g<<fixed;
        g<<setprecision(7)<<sol;
    }
    g.close();
    return 0;
}