A deranged algorithms professor has devised a terrible final exam: he throws his students into a strange maze formed entirely of linear and circular paths, with line segment endpoints and object intersections forming the junctions of the maze. The professor gives his students a map of the maze and a fixed amount of time to find the exit before he floods the maze with xerobiton particles, causing anyone still in the maze to be immediately inverted at the quantum level. Students who escape pass the course; those who don't are trapped forever in a parallel universe where the grass is blue and the sky is green.
The entrance and the exit are always at a junction as defined above. Knowing that clever ACM programming students will always follow the shortest possible path between two junctions, he chooses the entrance and exit junctions so that the distance that they have to travel is as far as possible. That is, he examines all pairs of junctions that have a path between them, and selects a pair of junctions whose shortest path distance is the longest possible for the maze (which he rebuilds every semester, of course, as the motivation to cheat on this exam is very high).
The joy he derives from quantumly inverting the majority of his students is marred by the tedium of computing the length of the longest of the shortest paths (he needs this to know to decide how much time to put on the clock), so he wants you to write a program to do it for him. He already has a program that generates the mazes, essentially just a random collection of line segments and circles. Your job is to take that collection of line segments and circles, determine the shortest paths between all the distinct pairs of junctions, and report the length of the longest one.
The input to your program is the output of the program that generates his mazes. That program was written by another student, much like yourself, and it meets a few of the professor's specifications:
1) No endpoint of a line segment will lie on a circle;
2)No line segment will intersect a circle at a tangent;
3) If two circles intersect, they intersect at exactly two distinct points;
4)Every maze contains at least two junctions; that is, a minimum maze is either a single line segment, or two circles that intersect.
There is, however, one bug in the program. (He would like to have it fixed, but unfortunately the student who wrote the code never gave him the source, and is now forever trapped in a parallel universe.) That bug is that the maze is not always entirely connected. There might be line segments or circles, or both, off by themselves that intersect nothing, or even little "submazes" composed of intersecting line segments and circles that as a whole are not connected to the rest of the maze. The professor insists that your solution account for this! The length that you report must be for a path between connected junctions!
Pictrue 1: Line segments only. The large dots are the junction pair
whose shortest path is the longest possible.
Pictrue 2: An example using circles only. Note that in this case there is
also another pair of junctions with the same length longest
possible shortest path.
Pictrue 3: Disconnected components.
Pictrue 4: Now the line segments are connected by a circle, allowing for
a longer shortest path.
An input test case is a collection of line segments and circles. A line segment is specified as "L X1 Y1 X2 Y2" where "L" is a literal character, and (X1,Y1) and (X2,Y2) are the line segment endpoints. A circle is specified by "C X Y R" where "C" is a literal character, (X,Y) is the center of the circle, and R is its radius. All input values are integers, and line segment and circle objects are entirely contained in the first quadrant within the box defined by (0,0) at the lower left and (100,100) at the upper right. Each test case will consist of from 1 to 20 objects, terminated by a line containing only a single asterisk. Following the final test case, a line containing only a single asterisk marks the end of the input.
For each input maze, output "Case N: ", where N is the input case number starting at one (1), followed by the length, rounded to one decimal, of the longest possible shortest path between a pair of connected junctions.
L 10 0 50 40
L 10 4 0 50 0
L 10 1 0 60 1 0
L 0 30 50 30
C 25 2 5 25
C 50 2 5 25
C 25 5 0 25
C 50 5 0 25
L 0 0 80 80
L 80 1 00 100 80
L 0 0 80 80
L 80 1 00 100 80
C 85 8 5 10
Ca se 1: 68.3
Ca se 2: 78.5
Ca se 3: 113.1
Ca se 4: 140.8
- 博客 在中国程序员是青春饭吗？
- 博客 程序员请照顾好自己，周末病魔差点一套带走我。
- 博客 Java基础知识面试题（2020最新版）
- 博客 和黑客斗争的 6 天！
- 博客 Intellij IDEA 实用插件安利
- 博客 搜狗输入法也在挑战国人的智商！
- 博客 总结了 150 余个神奇网站，你不来瞅瞅吗？
- 博客 副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
- 博客 MySQL数据库面试题（2020最新版）
- 博客 如果你是老板，你会不会踢了这样的员工？
- 博客 我入职阿里后，才知道原来简历这么写
- 博客 魂迁光刻，梦绕芯片，中芯国际终获ASML大型光刻机
- 博客 优雅的替换if-else语句
- 博客 离职半年了，老东家又发 offer，回不回？
- 博客 2020阿里全球数学大赛：3万名高手、4道题、2天2夜未交卷
- 博客 为什么你不想学习？只想玩？人是如何一步一步废掉的
- 博客 百度工程师，获利10万，判刑3年！
- 博客 程序员为什么千万不要瞎努力？
- 博客 为什么程序员做外包会被瞧不起？
- 博客 当HR压你价，说你只值7K，你该怎么回答？
- 博客 面试：第十六章：Java中级开发
- 博客 面试阿里p7，被按在地上摩擦，鬼知道我经历了什么？
- 博客 无代码时代来临，程序员如何保住饭碗？
- 博客 面试了一个 31 岁程序员，让我有所触动，30岁以上的程序员该何去何从？
- 博客 大三实习生，字节跳动面经分享，已拿Offer
- 博客 程序员垃圾简历长什么样？
- 博客 《Oracle Java SE编程自学与面试指南》最佳学习路线图2020年最新版（进大厂必备）
- 博客 字节跳动面试官竟然问了我JDBC？
- 博客 面试官：你连SSO都不懂，就别来面试了
- 博客 实时更新：计算机编程语言排行榜—TIOBE世界编程语言排行榜（2020年6月份最新版）