4837：Race

题目描述

度度熊最近参加了一场劲跑比赛，但是这个劲跑比赛的规则比较特殊。比赛方预先在地上画了一些横线和竖线（可以认为这些线为无限长的直线），要求选手从指定的位置出发，在最短时间内按照规定的顺序经过所有的直线（只要到达直线上的任意一点即为经过）。为了帮助度度熊获胜，你能为他规划一条最短的线路吗？

输入解释

第一行为T，表示输入数据组数。
下面T组数据。每组数据中：
第一行为一个整数n，表示有n条直线。接下来n行，每行包含两个整数，表示一条直线。如果直线为竖线，则第一个整数为0，第二个整数为直线的横坐标x。如果直线为横线，则第一个整数为1，第二个整数为直线的纵坐标y。度度熊将从平面的原点出发。

限制条件:
1<=T<=10
1<=n<=10^6
-500<=x,y<=500

输出解释

对第i组数据，输出
Case #i:
然后输出一个实数，表示从原点出发按输入顺序经过所有直线的最短路径的长度。保留到小数点后3位。

输入样例

输出样例

Case #1:
2.236

提示

度度熊需要按照规定的顺序经过所有的直线。如果度度熊不按照顺序经过直线，那么提前经过的直线是不算数的。
例如，假设度度熊需要按顺序经过直线1和直线2，那么如果度度熊在经过直线1之前经过了直线2，这是不算数的，
度度熊仍然需要在经过直线1后再次经过直线2。
但是度度熊可以经过直线1和直线2的交叉点而同时都算数。

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2014年百度之星程序设计大赛 - 复赛

源链接： HDU-4837

最后修改于 2020-10-25T23:17:18+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
20000/10000MS(Java/Others)	65535/65535K(Java/Others)