The Doors POJ - 1556

题目链接：The Doors

思路

题意：要求的是在一个空间内有许多墙，每个墙上有两扇门你要从最左边中点去最右边中点的最短路。

把每扇门看作是两个点然后利用计算几何的知识来判断一下两个点所形成的线段与图中的墙（也就是线段）有没有相交，规范相交与重合才算相交（对于非规范相交还要看是否重合），对于不相交的两个点之间建立边，然后跑dijkstra最短路即可。

两线段相交判定

//`两线段相交判断`
	//`2 规范相交`
	//`1 非规范相交`
	//`0 不相交`
	int segcrossseg(Line v) {
		int d1 = sgn((e - s) ^ (v.s - s));
		int d2 = sgn((e - s) ^ (v.e - s));
		int d3 = sgn((v.e - v.s) ^ (s - v.s));
		int d4 = sgn((v.e - v.s) ^ (e - v.s));
		if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;
		return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
			(d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
			(d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
			(d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
	}
	//`点和直线关系`
	//`1  在左侧`
	//`2  在右侧`
	//`3  在直线上`
	int relation(Point p) {
		int c = sgn((p - s) ^ (e - s));
		if (c < 0)return 1;
		else if (c > 0)return 2;
		else return 3;
	}
	//`两向量平行(对应直线平行或重合)`
	bool parallel(Line v) {
		return sgn((e - s) ^ (v.e - v.s)) == 0;
	}
	//`两直线关系`
	//`0 平行`
	//`1 重合`
	//`2 相交`
	int linecrossline(Line v) {
		if ((*this).parallel(v))
			return v.relation(s) == 3;
		return 2;
	}

主函数

const int N=3e3+5;
int n,cnt,head[N];
double dis[N];
bool vis[N];
struct edge{
	int next,to;
	double dis;
}e[N*N];
void add(int u,int v,double d){
	cnt++;	e[cnt].to=v;	e[cnt].dis=d;	e[cnt].next=head[u];	head[u]=cnt;
}
struct node{
	int pos;
	double dis;
	friend bool operator < (node a,node b){
		return a.dis>b.dis;
	}
};
void dijkstra(int st){
	for(int i=1;i<=N;i++)	dis[i]=1e9+7;
	memset(vis,0,sizeof(vis));
	priority_queue<node>q;
	q.push((node){st,0.0});
	dis[st]=0.0;
	while(!q.empty()){
		node t=q.top();
		q.pop();
		int x=t.pos;
		if(vis[x])	continue;
		vis[x]=true;
		for(int i=head[x];i;i=e[i].next){
			int j=e[i].to;
			if(dis[j]>dis[x]+e[i].dis){
				dis[j]=dis[x]+e[i].dis;
				q.push((node){j,dis[j]});
			}
		}
	}
}
int main(){
	while(scanf("%d",&n)){
		if(n==-1)	break;
		cnt=0;
		memset(head,0,sizeof(head));
		int p_cnt=0,l_cnt=0;
		for(int i=1;i<=n;i++){
			double x,y[4];
			scanf("%lf%lf%lf%lf%lf",&x,&y[0],&y[1],&y[2],&y[3]);
			for(int j=0;j<4;j++)	que[++p_cnt]=Point{x,y[j]};
			line[++l_cnt]=Line{{x,0.0},{x,y[0]}};
			line[++l_cnt]=Line{{x,y[1]},{x,y[2]}};
			line[++l_cnt]=Line({x,y[3]},{x,10.0});
		}
		que[++p_cnt]=Point{0.0,5.0};
		que[++p_cnt]=Point{10.0,5.0};
		for(int i=1;i<=p_cnt;i++){
			for(int j=1;j<=p_cnt;j++){
				Line t=Line{que[i],que[j]};
				bool flag=true;
				for(int k=1;k<=l_cnt;k++){
					if(t.segcrossseg(line[k])==2){
						flag=false;
						break;
					}
					if(t.segcrossseg(line[k])==1){
						if(t.linecrossline(line[k])==1){
							flag=false;
							break;
						}
					}
				}
				if(flag){
					double dis=que[i].distance(que[j]);
					add(i,j,dis);
					add(j,i,dis);
				}
			}
		}
		dijkstra(p_cnt-1);
		printf("%.2f\n",dis[p_cnt]);
	}
	return 0;
}