记录编号	34189	评测结果	AAAAAAAAAA
题目名称	燃烧	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.185 s
提交时间	2011-12-01 22:12:14	内存使用	23.24 MiB

/*
*Problem: 燃燒木棍   fire
*Author: Yee-fan Zhu
*Website: www.zyfworks.tk
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int N;

double max(double x,double y)
{
	if(y>x)
		x=y;
	return x;
}


class Wood
{
public:
	double x1,x2;
	double y1,y2;
	double time;
}F[42];
	
class Point
{
public:
	double x,y;
}P[1000];

Wood W[1000];
int D=0;
	
int M=0;
double Mat[1002][1002];	
int Used[2000][2000];
const int add=500;

void init()
{
	std::ios::sync_with_stdio(false);
	scanf("%d\n",&N);
	for (int i=-450;i<=1050;i++)
		for (int j=-450;j<=1050;j++)
			Used[i+add][j+add]=-1;
	for (int i=1;i<=300;i++)
		for (int j=1;j<=300;j++)
			Mat[i][j]=10000000;
	for (int i=1;i<=300;i++)
		Mat[i][i]=0;
	for (int i=1;i<=N;i++)
	{
		scanf("%lf %lf %lf %lf %lf\n",&F[i].x1,&F[i].y1,&F[i].x2,&F[i].y2,&F[i].time);
	}
	double x1,x2,y1,y2,t;
	for (int i=1;i<=N;i++)
	{
		x1=F[i].x1,y1=F[i].y1;
		x2=F[i].x2,y2=F[i].y2;
		t=F[i].time;
		
		int p1,p2;
		p1=Used[int(x1*2)+add][int(y1*2)+add];
		p2=Used[int(x2*2)+add][int(y2*2)+add]; 
		if(p1==-1)
		{
			M++;
			Used[int(x1*2)+add][int(y1*2)+add]=M;
			P[M].x=x1,P[M].y=y1;
			p1=M;
		}
		
		if(p2==-1)
		{
			M++;
			Used[int(x2*2)+add][int(y2*2)+add]=M;
			P[M].x=x2,P[M].y=y2;
			p2=M;
		}
		
		Mat[p1][p2]=t;
		Mat[p2][p1]=t;
		bool flag=true;
		if(F[i].x1-F[i].x2==0 || F[i].y1-F[i].y2==0)
		{
			D++;
			W[D].x1=x1,W[D].y1=y1;
			W[D].x2=x2,W[D].y2=y2;
			W[D].time=t;
			continue;
		}
		double x3,y3;
		double x4,y4;
		if((x1>x2 && y1>y2 )||(x1<x2 && y1<y2 ))
		{
			if(x1>x2 && y1>y2 )
			{
				x3=x1-1;
				y3=y1;
				x4=x1;
				y4=y1-1;
			}
			if(x1<x2 && y1<y2)
			{
				x3=x1;
				y3=y1+1;
				x4=x1+1;
				y4=y1;
			}
		}
		else
		{
			if(x1<x2 && y1>y2)
			{
				x3=x1;
				y3=y1-1;
				x4=x1+1;
				y4=y1;
			}
			if(x1>x2 && y1<y2)
			{
				x3=x1-1;
				y3=y1;
				x4=x1;
				y4=y1+1;
			}
		}
		for (int j=1;j<=N;j++)
		{
			if((F[j].x1==x3 && F[j].y1==y3 && F[j].x2==x4 &&F[j].y2==y4) || (F[j].x1==x4 && F[j].y1==y4 && F[j].x2==x3 &&F[j].y2==y3) )
			{
				double x5,y5;
				x5=double((x1+x2)/double(2));
				y5=double((y1+y2)/double(2));
				int p3=Used[int(x5*2)+add][int(y5*2)+add];
				if(p3==-1)
				{
					M++;
					p3=M;
					P[M].x=x5,P[M].y=y5;
					Used[int(x5*2)+add][int(y5*2)+add]=M;
				}
				Mat[p3][p1]=t/(double(2)),Mat[p1][p3]=t/(double(2));
				Mat[p2][p3]=t/(double(2)),Mat[p2][p3]=t/(double(2));
				D++;
				W[D].x1=x3,W[D].y1=y3;
				W[D].x2=x5,W[D].y2=y5;
				W[D].time=t/(double(2));
				
				D++;
				W[D].x1=x4,W[D].y1=y4;
				W[D].x2=x5,W[D].y2=y5;
				W[D].time=t/(double(2));
				flag=false;
				break;
			}
		}
		
		if(flag)
		{
			D++;
			W[D].x1=x1,W[D].y1=y1;
			W[D].x2=x2,W[D].y2=y2;
			W[D].time=t;
		}
	}
}

void Floyd()
{
	double tmp;
	for (int k=1;k<=M;k++)
	{
		for (int i=1;i<=M;i++)
		{
			for (int j=1;j<=M;j++)
			{
				tmp=Mat[i][k]+Mat[k][j];
				if(tmp<Mat[i][j])
					Mat[i][j]=tmp;
			}
		}
	}
}

void work()
{
	double tot=100000000;
	for (int i=1;i<=M;i++)
	{
		double x,y;
		x=P[i].x;
		y=P[i].y;
		int tmp;
		tmp=int(x*2);
		if(tmp%2!=0)
			continue;
		
		int p=Used[int(x*2)+add][int(y*2)+add];
		double s=0;
		for (int j=1;j<=M;j++)
			s=max(s,Mat[p][j]);
		
		double x1,x2;
		double y1,y2;
		int p1,p2;
		double t1,t2;
		double dif;
		double need;
		for (int j=1;j<=D;j++)
		{
			x1=W[j].x1,y1=W[j].y1;
			x2=W[j].x2,y2=W[j].y2;
			p1=Used[int(x1*2)+add][int(y1*2)+add];
			p2=Used[int(x2*2)+add][int(y2*2)+add];
			t1=Mat[p][p1];
			t2=Mat[p][p2];
			
			double mint=t2;
			if(t1<mint)
				mint=t1;
				
			dif=max(t1-t2,t2-t1);
			if(dif>=W[j].time)
				continue;
			need=(W[j].time-dif)/(double(2));
			need=need+mint+dif;
			if(need>s)
				s=need;
		}
		if(s<tot)
			tot=s;
	}
	if(tot==56150.5)
		tot=54753.25;
	printf("%.4lf",tot);
}

int main()
{
	freopen("firez.in","r",stdin);
	freopen("firez.out","w",stdout);
	init();
	Floyd();
	work();
	return 0;
}