#P903. 大突围
大突围
【问题背景】
——“队长,敌人越来越多,我们的人都快顶不住了!”
——“坚持住,只要再顶住5波进攻,我们的援军就要到了。”
——“恐怕不行了,队长,敌人的超级要塞已经出动了!”
——“什么?他们……”
——“不能再等了,撤吧!”
——“可是,我们真的能撤的出去吗?”
——“根据我的侦查,虽然敌人已经部署了严密的防线,我们绝不能靠近,不过可以绕过去。只要大家通过所有防线,就能回到大本营了……”
作为队长的zsc将军,面对着一个艰难的决定:是与敌人决一死战,还是趁着敌人的疏忽逃走?他需要你的帮助。
【问题描述】
根据侦察兵ck的观察,敌人在战场上共布置了n道防线,每条防线可以抽象为一条线段,这里用端点(p1 ,q1) (p2 ,q2 )来表示,不过在端点处无人值守,也就是可以通过端点。并且,无论你与防线距离多近,只要不在防线上,敌人都不会发现。你需要输出的是从原点(0,0)到给定终点(x,y)所需要的最少时间(这里认为行进速度为1个单位/s),但 不能穿过任何防线,这里的穿过是指存在一个时刻,部队位于防线上 。zsc将军会根据这个数据决定是否撤退。由于地形限制,军队只能经过第一象限及相邻坐标轴上的点。
【输入格式】
输入文件名为 death.in 。
第一行为一个整数n。
第二行,两个实数x,y,含义如描述。
接下来n行,每行四个整数表示每条防线的端点。
【输出格式】
输出文件名为 death.out 。
输出最少需要的时间,保留小数点后1位(直接去尾即可)。如果不能到达,输出“NO”。
【样例输入】
3
5 5
1 2 2 2
3 3 4 4
1 5 2 5
【样例输出】
7.2
【样例说明】
(0,0)->(1,2)->(5,5),总距离为sqrt(1* 1+2* 2)+sqrt(4* 4+3*3)≈7.2。
【数据规模与约定】
所有测试数据的范围和特点如下表所示
测试点编号 | n的规模 | 约定 |
---|---|---|
1 | ≤10 | 所有出现的坐标均不会超过10^6^ |
2 | ||
3 | ||
4 | ||
5 | ≤50 | |
6 | ||
7 | ||
8 | ||
9 | ||
10 | ||
11 | ||
12 | ||
13 | ≤200 | |
14 | ||
15 | ||
16 | ||
17 | ||
18 | ||
19 | ||
20 |