POJ-1556 The Doors

这道题，没想到什么好的办法，数据量不大，干脆直接转化成最短路问题

把每个列上的四个点放到点数组里，再加上起点和终点，再把每列的三个墙放到墙数组，再加上左墙和右墙

然后求两两点之间连成线段是否与墙数组的墙有超过两个交点，（因为和墙相接的缘故，总会有两个相交的）

不超过两个就在图中加一条边，代表两点相连，还有路径长度

最后迪杰斯特拉求解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const double eps=1e-8;
const double PI=acos(-1.0);
const int N=100;
int sgn(double x)
{
	if(fabs(x)<eps) return 0;
	if(x<0) return -1;
	else return 1;
}
struct Point
{
	double x,y;
	Point(){}
	Point(double _x,double _y)
	{
		x=_x;y=_y;
	}
	Point operator - (const Point &b) const
	{
		return Point(x-b.x,y-b.y);
	}
	//叉积
	double operator ^ (const Point &b) const
	{
		return x*b.y-y*b.x;
	}
	//点积
	double operator * (const Point &b) const
	{
		return x*b.x+y*b.y;
	}
	///绕原点旋转角度B（弧度值），后x,y的变化 
	void transXY(double B)
	{
		double tx=x,ty=y;
		x=tx*cos(B)-ty*sin(B);
		y=tx*sin(B)+ty*cos(B);
	}
}p[N];
struct Line
{  
	Point s,e;  
 	Line(){}  
 	Line(Point _s,Point _e)  {   s = _s;e = _e;  }  
 	//两直线相交求交点  
 	//第一个值为0表示直线重合，为1表示平行，为0表示相交,为2是相交 
 	 //只有第一个值为2时，交点才有意义     
 	pair<int,Point> operator &(const Line &b)const     
 	{        
 	    Point res = s;        
 	  	if(sgn((s-e)^(b.s-b.e)) == 0)      
 	    {            
 	    	if(sgn((s-b.e)^(b.s-b.e)) == 0)               
 	        	return make_pair(0,res);//重合           
 	        else return make_pair(1,res);//平行        
 	    }         
 	    double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));     
        res.x += (e.x-s.x)*t;    
 	    res.y += (e.y-s.y)*t;        
 	    return make_pair(2,res);     
 	}
}l[N];
double dist(Point a,Point b){return sqrt((a-b)*(a-b)); } 
//*判断线段相交 
bool inter(Line l1,Line l2) 
{
	return 
	max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&     
	max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&     
	max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&     
	max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&     
	sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 &&     
	sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0; 
}
struct node
{
	int id;
	double d;
	node(int a,double b)
	{
		id=a;d=b;
	}
	bool operator < (const node &u) const
	{
		return d<u.d;
	}
};
int n,pt,lt;
double ans[N];
double g[N][N];
void dj()
{
	priority_queue<node> q;
	q.push(node(0,0.0));
	while(!q.empty())
	{
		node u=q.top();
		q.pop();
		int p=u.id;
		for(int i=0;i<pt;i++)
		{
			if(i==p) continue;
			if(ans[i]>ans[p]+g[i][p])
			{
				ans[i]=ans[p]+g[i][p];
				q.push(node(i,ans[i]));
			}
		}
	}
}
int main()
{
	Point sta=Point(0.0,5.0);
	Point end=Point(10.0,5.0);
	while(~scanf("%d",&n))
	{
		if(n==-1) break;
		double x;
		Point a,b;
		pt=0,lt=0;
		p[pt++]=sta;
		for(int i=0;i<n;i++)
		{
			scanf("%lf%lf",&x,&b.y);
			a.x=x;b.x=x;a.y=0.0;
			p[pt++]=b;
			l[lt++]=Line(a,b);
			scanf("%lf%lf",&a.y,&b.y);
			l[lt++]=Line(a,b);
			p[pt++]=a;p[pt++]=b;
			scanf("%lf",&a.y);
			b.y=10.0;
			l[lt++]=Line(a,b);
			p[pt++]=a;
		}
		l[lt++]=Line(Point(0.0,0.0),Point(0.0,10.0));
		l[lt++]=Line(Point(10.0,0.0),Point(10.0,10.0));
		p[pt++]=end;
		for(int i=0;i<pt;i++)
			for(int j=0;j<pt;j++)
				g[i][j]=10000.0;
		for(int i=0;i<pt;i++)
			for(int j=i+1;j<pt;j++)
			{
				Line ll=Line(p[i],p[j]);
				int k=0,cnt=0;
				for(;k<lt;k++)
				{
					if(inter(ll,l[k])) cnt++;
					if(cnt>2) break;
				}
				if(k==lt) g[i][j]=g[j][i]=dist(p[i],p[j]);
			}
		for(int i=0;i<pt;i++) ans[i]=10000.0;
		ans[0]=0.0;
		dj();
		printf("%.2f\n",ans[pt-1]);
	}
	return 0;