Cod sursa(job #1722586)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 28 iunie 2016 14:50:42
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.02 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#define MAXN 600
#define MAXM 40
#define INF 1000000000
#define EPS 1e-8
using namespace std;
struct Point{
    int x;
    int y;
};
vector<Point> robot,obstacle[MAXM],nodes;
vector<pair<int,double> > g[MAXN];
Point start,finish;
int area[MAXM],seen[MAXN];
double best[MAXN];
int n,m;
int minimum(int a,int b){
    if(a<b)
        return a;
    return b;
}
int maximum(int a,int b){
    if(a>b)
        return a;
    return b;
}
int Semiplane(Point p){
    if(p.x>0||(p.x==0&&p.y>0))
        return 1;
    return 0;
}
bool Compare(Point a,Point b){
    int semiplane1=Semiplane(a),semiplane2=Semiplane(b);
    return semiplane1<semiplane2||(semiplane1==semiplane2&&a.y*b.x<a.x*b.y);
}
int Determinant(Point a,Point b,Point c){
    return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
}
vector<Point> Build(const vector<Point>& oldObstacle){
    int i;
    vector<Point> temp,newObstacle,answer;
    Point a={INF,INF},b={INF,INF},c={-INF,-INF};
    for(i=1;i<robot.size();i++)
        temp.push_back({robot[i-1].x-robot[i].x,robot[i-1].y-robot[i].y});
    temp.push_back({robot[robot.size()-1].x-robot[0].x,robot[robot.size()-1].y-robot[0].y});
    for(i=1;i<oldObstacle.size();i++)
        temp.push_back({oldObstacle[i].x-oldObstacle[i-1].x,oldObstacle[i].y-oldObstacle[i-1].y});
    temp.push_back({oldObstacle[0].x-oldObstacle[oldObstacle.size()-1].x,oldObstacle[0].y-oldObstacle[oldObstacle.size()-1].y});
    sort(temp.begin(),temp.end(),Compare);
    for(i=0;i<robot.size();i++){
        if(robot[i].y<a.y)
            a=robot[i];
        if(robot[i].x<b.x||(robot[i].x==b.x&&robot[i].y<b.y))
            b=robot[i];
    }
    for(i=0;i<oldObstacle.size();i++)
        if(oldObstacle[i].x>c.x||(oldObstacle[i].x==c.x&&oldObstacle[i].y>c.y))
            c=oldObstacle[i];
    c.y=c.y-b.y+a.y;
    newObstacle.push_back(c);
    for(i=0;i<temp.size()-1;i++)
        newObstacle.push_back({newObstacle[i].x+temp[i].x,newObstacle[i].y+temp[i].y});
    answer.push_back(newObstacle[0]);
    answer.push_back(newObstacle[1]);
    for(i=2;i<newObstacle.size();i++){
        if(Determinant(answer[answer.size()-1],answer[answer.size()-2],newObstacle[i])==0)
            answer.pop_back();
        answer.push_back(newObstacle[i]);
    }
    return answer;
}
double Distance(Point a,Point b){
    return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool IsOnLine(Point p,Point a,Point b){
    if(fabs(Distance(p,a)+Distance(p,b)-Distance(a,b))<EPS)
        return true;
    return false;
}
bool Intersect(Point a,Point b,Point c,Point d){
    long long value1,value2;
    if(maximum(minimum(a.x,b.x),minimum(c.x,d.x))>minimum(maximum(a.x,b.x),maximum(c.x,d.x)))
        return false;
    if(maximum(minimum(a.y,b.y),minimum(c.y,d.y))>minimum(maximum(a.y,b.y),maximum(c.y,d.y)))
        return false;
    value1=1LL*Determinant(a,b,c)*Determinant(a,b,d);
    value2=1LL*Determinant(c,d,a)*Determinant(c,d,b);
    if(value1<0&&value2<0)
        return true;
    return false;
}
bool InObstacle(Point p,int index){
    int i,currentArea=abs(Determinant(p,obstacle[index][0],obstacle[index][obstacle[index].size()-1]));
    if(IsOnLine(p,obstacle[index][0],obstacle[index][obstacle[index].size()-1]))
        return false;
    for(i=1;i<obstacle[index].size();i++){
        currentArea+=abs(Determinant(p,obstacle[index][i],obstacle[index][i-1]));
        if(IsOnLine(p,obstacle[index][i],obstacle[index][i-1]))
            return false;
    }
    if(currentArea==area[index])
        return true;
    return false;
}
bool IsLine(Point a,Point b){
    int i,j,k;
    for(i=0;i<m;i++){
        if(InObstacle(a,i)||InObstacle(b,i))
            return false;
        for(j=0;j<obstacle[i].size();j++)
            for(k=j+1;k<obstacle[i].size();k++)
                if(Intersect(a,b,obstacle[i][j],obstacle[i][k]))
                    return false;
    }
    return true;
}
void BuildGraph(){
    int i,j,nodeCount;
    nodes.push_back(start);
    for(i=0;i<m;i++){
        area[i]=Determinant({0,0},obstacle[i][obstacle[i].size()-1],obstacle[i][0]);
        nodes.push_back(obstacle[i][0]);
        for(j=1;j<obstacle[i].size();j++){
            area[i]+=Determinant({0,0},obstacle[i][j-1],obstacle[i][j]);
            nodes.push_back(obstacle[i][j]);
        }
    }
    nodes.push_back(finish);
    nodeCount=nodes.size();
    for(i=0;i<nodeCount;i++)
        for(j=i+1;j<nodeCount;j++)
            if(IsLine(nodes[i],nodes[j])){
                g[i].push_back(make_pair(j,Distance(nodes[i],nodes[j])));
                g[j].push_back(make_pair(i,Distance(nodes[j],nodes[i])));
            }
}
void BellmanFord(){
    int i,j,node,nodeCount=nodes.size();
    for(i=1;i<nodeCount;i++)
        best[i]=INF;
    for(i=0;i<nodeCount&&seen[nodeCount-1]==0;i++){
        node=0;
        for(j=1;j<nodeCount;j++)
            if(seen[j]==0&&(best[j]<best[node]||seen[node]==1))
                node=j;
        for(j=0;j<g[node].size();j++)
            if(best[node]+g[node][j].second<best[g[node][j].first])
                best[g[node][j].first]=best[node]+g[node][j].second;
        seen[node]=1;
    }
}
int main(){
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    int i,j,vertices;
    Point p;
    scanf("%d",&n);
    start.x=start.y=INF;
    for(i=0;i<n;i++){
        scanf("%d%d",&p.x,&p.y);
        start.x=minimum(start.x,p.x);
        start.y=minimum(start.y,p.y);
        robot.push_back(p);
    }
    scanf("%d",&m);
    for(i=0;i<m;i++){
        scanf("%d",&vertices);
        for(j=0;j<vertices;j++){
            scanf("%d%d",&p.x,&p.y);
            obstacle[i].push_back(p);
        }
    }
    scanf("%d%d",&finish.x,&finish.y);
    for(i=0;i<m;i++)
        obstacle[i]=Build(obstacle[i]);
    BuildGraph();
    BellmanFord();
    if(best[nodes.size()-1]==INF){
        printf("-1");
        return 0;
    }
    printf("%.2f",best[nodes.size()-1]);
    return 0;
}