poj 1556 The door

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1000;
const int maxe = 20000;
const int INF = 0x3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1.0);

struct Point{
    double x,y;
    Point(double x=0, double y=0) : x(x),y(y){ }    //构造函数
};
typedef Point Vector;

Vector operator + (Vector A , Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Vector A , Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (Vector A , double p){return Vector(A.x*p,A.y*p);}
Vector operator / (Vector A , double p){return Vector(A.x/p,A.y/p);}

bool operator < (const Point& a,const Point& b){
    return a.x < b.x ||( a.x == b.x && a.y < b.y);
}

int dcmp(double x){
    if(fabs(x) < eps) return 0;
    else              return x < 0 ? -1 : 1;
}
bool operator == (const Point& a, const Point& b){
    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

///向量（x,y）的极角用atan2(y,x);
double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }
double Length(Vector A)    { return sqrt(Dot(A,A)); }
double Angle(Vector A, Vector B)  { return acos(Dot(A,B) / Length(A) / Length(B)); }

double Cross(Vector A, Vector B)  { return A.x*B.y - A.y * B.x; }
double Area2(Point A,Point B,Point C) { return Cross(B-A,C-A); }


bool SegmentIntersection(Point a1, Point a2, Point b1, Point b2) {
    bool flag = max(a1.x, a2.x) >= min(b1.x, b2.x) && max(b1.x, b2.x) >= min(a1.x, a2.x) &&
                max(a1.y, a2.y) >= min(b1.y, b2.y) && max(b1.y, b2.y) >= min(a1.y, a2.y);
    double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1),
           c3 = Cross(b2-b1,a1-b1), c4 = Cross(b2-b1,a2-b1);
    return flag && dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){
    double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1),
           c3 = Cross(b2-b1,a1-b1), c4 = Cross(b2-b1,a2-b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

struct Edge{
    int u,v;
    double w;
    int next;
    void assign(int u_,int v_,double w_,int next_){
        u = u_;  v = v_;  w = w_;  next = next_;
    }
    bool operator < (const Edge& r) const{
         return  w > r.w;
    }
}edges[maxe];

struct Dijkstra{
    int s,t;
    int head[maxn];
    int cnt;
    double d[maxn];

    void addedge(int u,int v,double w){
        edges[cnt].assign(u,v,w,head[u]);
        head[u] = cnt++;
    }

    void init(int s_,int t_){
        s = s_;   t = t_;
        cnt = 0;
        memset(head,-1,sizeof(head));
    }

    double dijkstra(){
        priority_queue<Edge> Q;
        while(!Q.empty())  Q.pop();
        for(int i=1;i<=maxn;i++)  d[i] = INF;
        bool vis[maxn];
        memset(vis,0,sizeof(vis));
        Edge edge = {s,0,0};
        Q.push(edge);  d[s] = 0;
        while(!Q.empty()){
            Edge e = Q.top() ; Q.pop() ;
            int u = e.u;
            if(vis[u]) continue;
            vis[u] = true;
            for(int i=head[u];i!=-1;i=edges[i].next){
                int v = edges[i].v;
                if( d[v] > d[u] + edges[i].w){
                    d[v] = d[u] + edges[i].w;
                    Edge edge = {v,0,d[v]};
                    Q.push(edge);
                }
            }
        }
        return d[t];
    }
};

/************************分割线****************************/

Point P[maxn][4];
int n;
Dijkstra solver;
int main()
{
    //freopen("E:\acm\input.txt","r",stdin);

    while(cin>>n && n != -1){
        solver.init(1,4*n+2);
        P[0][0] =Point(0,5);   P[n+1][0] =Point(10,5);
        for(int i=1;i<=n;i++){
            double x,y;
            scanf("%lf",&x);
            for(int j=0;j<=3;j++){
             scanf("%lf",&y);
             P[i][j]=Point(x,y);
           }
        }

        for(int i=0;i<=n;i++){
            if(i==0){
                for(int j=i+1;j<=n;j++)
                   for(int k=0;k<=3;k++){
                       int flag = true;
                       for(int m=1;m<=j-1;m++){
                          Point a1=P[m][0],a2=P[m][1],b1=P[m][2],b2=P[m][3];
                          if(!SegmentIntersection(P[0][0],P[j][k],a1,a2) && !SegmentIntersection(P[0][0],P[j][k],b1,b2)){
                              flag = false;   break;
                          }
                       }
                       if(flag){
                          solver.addedge(1,4*j+k-2,Length(P[0][0]-P[j][k]));
                       }
                   }
               int flag = true;
               for(int m=1;m<=n;m++){
                  Point a1=P[m][0],a2=P[m][1],b1=P[m][2],b2=P[m][3];
                  if(!SegmentIntersection(P[0][0],P[n+1][0],a1,a2) && !SegmentIntersection(P[0][0],P[n+1][0],b1,b2)){
                      flag = false;   break;
                  }
               }
               if(flag){
                  solver.addedge(1,4*n+2,Length(P[0][0]-P[n+1][0]));
               }

            }
            else{
               for(int h=0;h<=3;h++){  //确定点P[i][h]
                   for(int j=i+1;j<=n;j++)
                   for(int k=0;k<=3;k++){   //确定点p[j][k];
                       int flag = true;
                       for(int m=i+1;m<=j-1;m++){
                          Point a1=P[m][0],a2=P[m][1],b1=P[m][2],b2=P[m][3];
                          if(!SegmentIntersection(P[i][h],P[j][k],a1,a2)&&!SegmentIntersection(P[i][h],P[j][k],b1,b2)){
                              flag = false;   break;
                          }
                       }
                       if(flag){
                          solver.addedge(4*i+h-2,4*j+k-2,Length(P[i][h]-P[j][k]));
                       }
                   }
                   int flag = true;
                   for(int m=i+1;m<=n;m++){
                      Point a1=P[m][0],a2=P[m][1],b1=P[m][2],b2=P[m][3];
                      if(!SegmentIntersection(P[i][h],P[n+1][0],a1,a2)&&!SegmentIntersection(P[i][h],P[n+1][0],b1,b2)){
                          flag = false;   break;
                      }
                   }
                   if(flag){
                      solver.addedge(4*i+h-2,4*n+2,Length(P[i][h]-P[n+1][0]));
                   }
               }
            }
        }
        printf("%.2f
",solver.dijkstra());
    }
}
View Code