欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ-1556 The Doors

程序员文章站 2022-04-02 16:56:36
...

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

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

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

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

最后迪杰斯特拉求解

#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;