1665.cpp

acm-pku-1665 the doors

#include<stdio.h>
#include<string.h>
#include<math.h>

int count;
double path[20][5];
double pos[20][6];

int connect(double x1,double y1,double x2,double y2,int from,int end)
{
	int n;
	double m=0;
	for(n=1;n<=count;n++)
	{
		if(n>from&&n<end)
		{
			m=(pos[n][4]-x1)*(y2-y1)/(x2-x1)+y1;	
			if(m>pos[n][0]&&m<pos[n][1]
				||m>pos[n][2]&&m<pos[n][3]) continue;
			else return 0;
		}
	}
	return 1;
}

double DFS(int i,int j)
{
	double temp,min,len;
	int x,y,k,test;
	if(connect(pos[i][4],pos[i][j],10,5,i,20))
	{
		len=sqrt((pos[i][4]-10)*(pos[i][4]-10)+(pos[i][j]-5)*(pos[i][j]-5));
		if(path[i][j]<0) { path[i][j]=len; return len;}
	}

	for(x=i+1;x<=count;x++)
	{
		min=1000000000;
		for(y=0;y<4;y++)
		{
			len=sqrt((pos[x][4]-pos[i][4])*(pos[x][4]-pos[i][4])+
				(pos[x][y]-pos[i][j])*(pos[x][y]-pos[i][j]));
			if(path[x][y]>0) temp=path[x][y];
			else             temp=DFS(x,y);
			if(min>temp+len) min=temp+len;
		}
		for(k=x+1;k<=count;k++)
		{
			for(y=0,test=1;y<4;y++)
			{
				if(connect(pos[i][4],pos[i][j],pos[k][4],pos[k][y],i,k))
				{
					len=sqrt((pos[k][4]-pos[i][4])*(pos[k][4]-pos[i][4])+
						(pos[k][y]-pos[i][j])*(pos[k][y]-pos[i][j]));
					if(path[k][y]>0) temp=path[k][y];
					else             temp=DFS(k,y);
					if(min>temp+len) min=temp+len;
					test=0;
				}
			}
			if(test) break;
		}
		if(path[i][j]<0)        path[i][j]=min;
		else if(path[i][j]>min) path[i][j]=min; 
		return path[i][j];
	}
}


int main()
{
	int n,m,i,j;
	while(1)
	{
		scanf("%d",&n);
		if(n<0) break;
		else if(n==0) { printf("10.00\n"); continue;}
		for(i=0;i<20;i++) for(j=0;j<5;j++) path[i][j]=-1;
		for(m=1;n>0;n--,m++)
		{
			scanf("%lf",&pos[m][4]);
			for(i=0;i<4;i++) scanf("%lf",&pos[m][i]);
		}
		count=m-1;
		pos[0][4]=0;
		pos[0][0]=5;
		printf("%.2lf\n",DFS(0,0));
	}
	return 0;
}