回答 1 已采纳 Problem Description
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
回答 1 已采纳 Description
There is a mysterious planet called Yaen, whose space is 2-dimensional. There are many beautiful stones on the planet, and the Yaen people love to collect them. They bring the stones back home and make nice mobile arts of them to decorate their 2-dimensional living rooms.
In their 2-dimensional world, a mobile is defined recursively as follows:
a stone hung by a string, or
a rod of length 1 with two sub-mobiles at both ends; the rod is hung by a string at the center of gravity of sub-mobiles. When the weights of the sub-mobiles are n and m, and their distances from the center of gravity are a and b respectively, the equation n * a = m * b holds.
For example, if you got three stones with weights 1, 1, and 2, here are some possible mobiles and their widths:
Given the weights of stones and the width of the room, your task is to design the widest possible mobile satisfying both of the following conditions.
It uses all the stones.
Its width is less than the width of the room.
You should ignore the widths of stones.
In some cases two sub-mobiles hung from both ends of a rod might overlap (see the figure on the right). Such mobiles are acceptable. The width of the example is (1/3) + 1 + (1/4).
The first line of the input gives the number of datasets. Then the specified number of datasets follow. A dataset has the following format.
r is a decimal fraction representing the width of the room, which satisfies 0 < r < 10. s is the number of the stones. You may assume 1 <= s <= 6. wi is the weight of the i-th stone, which is an integer. You may assume 1 <= wi <= 1000.
You can assume that no mobiles whose widths are between r - 0.00001 and r + 0.00001 can be made of given stones.
For each dataset in the input, one line containing a decimal fraction should be output. The decimal fraction should give the width of the widest possible mobile as defined above. An output line should not contain extra characters such as spaces.
In case there is no mobile which satisfies the requirement, answer -1 instead.
The answer should not have an error greater than 0.00000001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.
回答 1 已采纳 Description
Input any five positive integral numbers n1, n2, n3, n4, n5, such that 0<=ni<=100, 1<=i<=5. To the first four positive integral numbers (n1, n2, n3, n4) the arithmetic operation, such as addition (+), subtraction (-), multiplication (*), or division (/) and brackets ('(',')') may be freely applied, but in the arithmetic expression formed with these numbers and operations, every one of the four integral numbers should be used once and only once.
Write a program for finding an arithmetic expression that satisfies the above requirement and equals n5.
The input file consists of a number of data sets.Each data set is a line of 5 numbers separated by blank.A line of a single -1 represents the end of input.
For each data set output the original data set first.If the program finds out the expression for these four arbitrary input numbers, then it gives out the output "OK!"；On the contrary, if the program could not get the result of n5 by any arithmetic operations to the four input numbers, it gives output "NO!".
1 2 3 4 50
2 3 10 1 61
1 2 3 4 50 NO!
2 3 10 1 61 OK!