这就是最终的题了，跟原题有那么一些出入，不过基本的条件和约束都没有变化。
顺手写了一个GUI，改天发个sample上来，呵呵。
题目是我出的，不过一开始竟然没想明白怎么做，大大的土了一把。
存照纪念之。
1.好心的出租车司机
北京的一位出租车司机向你抱怨：城市发展太快，公路越来越多，他已经疲于计算行驶路线，于是求助你开发一个自动导航的工具。
出租车只能在公路上行驶。所有的公路都是笔直、双向的，相交的公路视为连通（可以在交叉点处从一条公路开到另一公路上）。由于道路施工，整个城市的公路系
统可能并不完全通畅。如果乘客的目的地不在公路边，则乘客下车后要步行前往，步行路线不受公路限制。这位好心的司机还特别提出，乘客步行距离越短越好；其
次，出租车行驶里程越短越好。
方便起见，用笛卡儿坐标系来描述城市地图，所有坐标都在第一象限[0, 10000]的范围内。公路宽度忽略不计。
输入格式
第一行是一个正整数k，代表公路条数。以下k行每行用4个非负整数描述一条公路（用空格隔开），前两个表示公路起点的坐标，后两个表示公路终点的坐标。下一行包含4个非负整数（用空格隔开），前两个表示乘客上车点（保证在某条公路上），后两个表示乘客目的地坐标。
输出格式
仅一行，为出租车行驶的里程数，保留一位小数（四舍五入）。
输入样例 例
2
2 2 10 10
10 2 2 10
3 3 9 4
输出样例 例
7.8
评分规则
- 程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过1秒，否则该用例不得分；
- 要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
- 本题包含20个测试点，前10组满足k<=10，后10组满足k<=50。每个测试点10分，共200分。
0 评论:
Post a Comment