胖子过走廊
有一条横向的走廊，长200米，宽100米。在走廊中分布着一些柱子，给要通过的人造成一定的麻烦。瘦的人，有可能一次走到底，顺利地通过走廊。胖子就倒霉了，往往走了一大半的路，前面突然出现一大群柱子，再也走不过去了，只好“回头是岸”。最气人的是，完全有可能无论这位胖子如何走，他也不可能通过这条走廊。现在要求你为胖子们编写一个程序，算出能通过走廊最胖的胖子的直径。（假设柱子的直径可以忽略不计，而胖子也可以认为是一个不可伸缩的大圆球。）
左
端
下 端
程序要求如下：
1、数据从文本文件fatman.txt中读取。
文件格式为：首先一行为一个整数N，
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示有N根柱子。当 N=0 时表示数据输入结束。以后N行每行包括两个整数x、y表示第N根柱子的坐标。x表示柱子离走廊左端X米，y表示柱子离走廊下端Y米，两数之间用空格隔开。然后是另一个整数N，表示另一组输入数据的开始。（1< N <=200）
2、结果输出到屏幕，每个结果占一行，要求小数点后至少保留5位。
输入范例： 输出范例： 编程思路：
8 29.68164 将柱子的位置视为点，距离走廊左端、下端
10 70 的长度即该点的横、纵坐标。各点连接可以构成
20 85 许多不同的路径，我们只观察那些从下端能到达30 17 上端，且无回头方向的完整路径。每一条路径都40 86 有一条最长的线段(即柱子与柱子之间的距离) , 50 45 将所有路径的最长线段选取出来，其中最短的60 68 那条，就是能通过走廊最胖的胖子的直径。
75 29
80 90 本程序采用递归算法：先把各点按纵坐标从
0 小到大排序，以最下端的点为基准点。从基准点出发，寻找纵坐标比它大的点作为当前基准点。调用递归函数顺序连接比当前基准点纵坐标大的点，直至最上端。记录这条路径上的最长线段(即柱子与柱子之间的最大距离)，返回递归调用，再连接其他比当前基准点纵坐标大的点，一直到最上端的点成为基准点为止。将每次记录的最长线段与前次相比，取其短者参与下一次比较。最后得到的最短者即为所求。
浙公网安备 33021202002483