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

题目详情

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

▼优质解答

答案和解析

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

看了一道tyvj编程题背景Bac...的网友还看了以下：

7/10×7表示（7/10的7倍是多少）,1/3×4/5表示（1/3的4/5是多少）,7/10÷7 　2020-04-09 …

老师要求五位学生背诵常见的1000个英文单词．已知A生背对950个，B生背对925个，C生背对90 　2020-07-09 …

课本背面的ISBN978-7-303-06361-7|G.4683中,ISBN表示的意思是(),I 　2020-07-19 …

7×1/9表示(）,1/9×7表示（）.这个题目我是这样填的：(7个1/9相加的和是多少）,（1/ 　2020-07-19 …

X立方-X平方+2X+7表示,或a（x-1）立方+b(x-1)平方+c(x-1)+d,那么abcd 　2020-07-22 …

图7为某山地部分等高线、7月等温线及雪线示意图。读图回答11～12题。11．该山地南坡的坡向最可能是　2020-12-05 …

小名和爸爸准备了一些同样的可乐瓶(每瓶装水1.25千克),去上山背水.回来时他们共背水25千克,小明　2020-12-06 …

怎样能背圆周率最块啊我圆周率在第一天背到100位,第二天背到了150位,第三天背到200位,可到了第　2020-12-12 …

在70007000700中，左边的7表示，中间的7表示，右边的7表示A.7个百B.7000万C.7个　2020-12-21 …