一道tyvj编程题背景Background描述Description有一块777*777的方形海域,左下角坐标为（0,0）,右上角为（777,777）.海域内有N艘敌军军舰.海域内任意一点都有一个危险度,计算方式为100/d,d表示离此

Question

一道tyvj编程题
背景 Background
描述 Description 有一块777*777的方形海域,左下角坐标为（0,0）,右上角为（777,777）.海域内有N艘敌军军舰.海域内任意一点都有一个危险度,计算方式为100/d,d表示离此点最近的一搜军舰与此点的距离（直线距离）.小R,接到这样一个任务,他要驾船从方形海域的右边界进入,从左边界出来,任务的航线可以是一任意弯曲的线条,但是其间不能离开海域.整个任务的危险度等于路经的危险度最大的点的危险度,称之为“任务危险度”.现在小R得到了所有N艘军舰的具体坐标,你能帮他求出可能的最小“任务危险度”是多少吗?
输入格式 InputFormat 多组数据!
第一行,一个整数：N（1

Answer 1

题目要求最小任务危险度,而且要保留两位小数,由此可以考虑二分算法.
每次枚举一个d,然后验证d能否行.关键在于d的验证问题上,这个可以对每个敌军军舰求一下危险范伟d,如果所有n的军舰的范伟能涵盖整个上下方向的地图证明此时的d无法使船通过,那么要继续向下二分,直到分到一个最大的满足题意的d,然后答案就是100/d.注意下精度就好了,0.000001就没问题.
有必要代码的话,追问给你写个.