TopCoder problem "NegativePhotoresist" used in SRM 210 (Division I Level Three)



Problem Statement

    

You are responsible for fabricating a circuit board for an engineering firm. The circuit consists of pinholes (where pins of various components will be inserted) connected by metal traces. For this problem, assume that pinholes can be treated as points in a plane and metal traces can be treated as straight line segments connecting two pinholes.

A highly simplified description of the fabrication process follows. The circuit pattern is cut out of a sheet of opaque material, forming a mask. A sheet of metal is covered with a thin film of material, called negative photoresist, that hardens when exposed to ultraviolet light. The mask is placed over the photoresist and illuminated with ultraviolet light, hardening the photoresist where the light passes through the mask. Finally, the metal sheet is bathed in an etching solution, which destroys the metal except where it is protected by hardened photoresist. The remaining metal forms the circuit.

After a long period of carefully laying out the circuit board, you have the mask prepared. Just before you illuminate the photoresist with ultraviolet light, your boss rushes in and gives you some last minute requirements: the sum of the lengths of the shortest metal trace paths between each pair of pinholes must be under a certain limit, and the board has to be ready by tomorrow. In other words, if you find the shorest path between every pair of connected pins, the sum of the lengths of all these shortest paths must be under the limit. There is no way you can redesign everything in one day, so you decide to improvise. By tilting the mask around its x-axis before you illuminate the photoresist, the circuit will be shrunk along the y-direction; only the projection of the mask on the plane of the photoresist is important since you are shining light through it (assume the light rays are parallel to the z-axis and ignore diffraction effects). Since this also moves the locations of the pins, you want to tilt the mask as little as possible.

Write a class NegativePhotoresist with a method minimumTilt that takes a String[] pinConnections specifying for each pinhole its mask-plane coordinates and its connections to other pinholes and an int limit, and returns as a double the minimum non-negative angle (in radians) the mask must be rotated around the x-axis such that the sum of the lengths of the shortest paths between each pair of pinholes is less than limit. If there is no path between a pair of pinholes, omit that pair from the sum.

Each element of pinConnections corresponds to one pinhole. Element i will begin with a pair of integers specifying the x and y coordinates of pinhole i separated by a single comma. Following this is a space-separated list of zero or more integers specifying the zero-based indices of the pinholes that i connects to. All integers are non-negative and may have leading zeroes. For this problem, pinholes are directly connected if and only if they are specified to connect in pinConnections. In other words, overlapping or coinciding metal traces do not create a connection.

 

Definition

    
Class:NegativePhotoresist
Method:minimumTilt
Parameters:String[], int
Returns:double
Method signature:double minimumTilt(String[] pinConnections, int limit)
(be sure your method is public)
    
 

Notes

-A return value with either an absolute or relative error of less than 1e-9 radians is considered correct.
-There can only be up to one connection between a pair of pinholes. If an index j appears multiple times in element i of pinConnections, there is still only one metal trace between pinholes i and j.
-The sum over all pairs of the shortest path lengths will be minimized when the mask is rotated by Pi / 2 radians.
-Pairs are unordered. The pair (pinhole i, pinhole j) is the same as (pinhole j, pinhole i).
 

Constraints

-The correct answer will be between 0.01 and 1.55, inclusive.
-pinConnections will contain between 2 and 50 elements, inclusive.
-Elements of pinConnections will contain at most 50 characters.
-Elements of pinConnections will be formatted "X,Y P1 P2 P3 ..." (quotes are for clarity) where X and Y are between 0 and 100000 inclusive, and each of the indices Pj will be separated by a single space and will be between 0 inclusive and the number of elements in pinConnections exclusive.
-If pinhole i connects to pinhole j, pinhole j will also connect to pinhole i.
-A pinhole will not connect to itself.
-limit will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
{"3,0 2 3",
"13,0 2 3",
"0,2 0 1",
"8,50 0 1",
"3,100000 5",
"100000,3 4",
"8432,221"}
100835
Returns: 1.4454078077996135
Pinholes 0, 2, 1, and 3 form a cycle (in that order). When the mask is laid flat, the shortest path between pinholes 0 and 1 goes through pinhole 2. However, if the mask is tilted by more than 1.4454039026103331 radians, the shortest path between pinholes 0 and 1 switches to go through pinhole 3. The shortest path between pinholes 2 and 3 always goes through pinhole 0, regardless of the angle. Pinholes 4 and 5 form a separate component that contains only one connection. Pinhole 6 is not connected to anything, and therefore does not influence the total path length.
1)
    
{"3,0 2 3",
"13,0 2 3",
"0,2 0 1",
"8,50 0 1",
"3,100000 5",
"100000,3 4",
"8432,221"}
141601
Returns: 0.010604469396671205
This is the same mask as in Example 0. It only has to be tilted slightly to achieve a total shortest path length of 141601.
2)
    
{"3,0 2 3",
"13,0 2 3",
"0,2 0 1",
"8,50 0 1",
"3,100000 5",
"100000,3 4",
"8432,221"}
100065
Returns: 1.5491503047781332
This is the same mask as in Example 0. It has to be tilted until it is almost standing on its edge to achieve a total shortest path length of 100065.
3)
    
{"76492,66181 1",
"74004,26736 0 14",
"22967,14922",
"5781,62226",
"82836,93961 23",
"87218,72769 19",
"93356,54263 21 23",
"31487,92953",
"4108,40237 25",
"90459,36018 18",
"86769,8014",
"6311,25772 13",
"9507,63470 20",
"30653,48087 11 15",
"84214,63941 1",
"87079,8036 13",
"10892,10164 25 23",
"31650,57394",
"12181,22580 9",
"8820,66849 5",
"63222,10057 12",
"85163,78521 6",
"73264,56781",
"45982,63119 4 6 16",
"96653,33496",
"4728,75705 8 16",
"93821,30582",
"9948,22812"}
2198136
Returns: 1.078664288678656
4)
    
{"26749,31005 7 12 37 22 3 31 18 14 22 43 18 47 27",
"89443,23479 37 20 18 45 4 28 45 48 45 48 42 43",
"26624,91482 8 10 9 47 38 7 26 38 7 15 24 33 13 19",
"74780,3281 5 35 24 0 32 6 7 40 16 44 27 29 27 42",
"64491,34646 12 42 9 10 25 1 14 22 32 28 16 24 49",
"57611,97350 3 6 16 38 37 26 7 46 47 9 34 17 36 33",
"54900,19650 5 41 17 21 3 41 45 9 45 24 7 29 49 33",
"37779,84466 30 37 0 43 36 2 5 45 31 2 3 13 17 6 27",
"68486,19205 2 14 42 44 17 34 25 41 38 43 10 49 11",
"86915,28119 21 31 2 40 31 12 49 41 4 22 5 34 6 46",
"81402,18667 40 2 17 17 18 8 4 12 38 12 15 26 42 12",
"76982,50425 29 29 13 8 36 49 16 27 26 28 27 34 46",
"43766,59005 15 27 0 9 4 22 10 10 49 44 37 10 34 24",
"71619,57051 36 47 48 39 11 45 32 42 30 7 29 2 34",
"95436,51350 8 18 23 22 17 23 22 16 0 48 19 4 24 19",
"18419,71778 29 12 31 23 24 30 36 26 10 18 45 36 2",
"58370,12207 48 33 5 14 19 47 11 28 44 3 18 32 4 46",
"93954,84580 33 21 10 8 47 35 32 6 10 14 43 22 5 7",
"37005,46508 14 29 22 1 10 0 23 37 15 0 31 16 31 41",
"25700,33156 20 25 35 40 38 16 14 22 14 23 27 25 2",
"87882,64415 19 35 35 33 1 24 26 24 34 41 34 31 29",
"80610,20042 9 27 35 28 46 17 37 28 36 37 6 41 34",
"55546,68119 39 18 34 14 12 0 14 9 0 17 39 4 19 27",
"12701,80882 30 32 15 14 37 42 14 47 18 33 47 19 46",
"14048,1355 15 20 20 3 28 42 14 12 2 49 45 25 6 4",
"27482,63293 49 38 45 19 8 39 4 38 47 38 46 19 24",
"48215,66574 35 41 32 30 20 41 5 2 15 35 10 11 49",
"53613,76037 21 12 40 11 42 46 0 3 49 11 19 3 22 7",
"90922,15011 21 30 40 40 40 21 44 24 1 16 4 11 49",
"67445,91022 15 11 35 47 18 11 38 20 13 38 3 32 6",
"93451,40067 41 23 7 28 26 47 42 15 44 49 31 13 31",
"25947,11589 9 15 9 40 39 0 30 7 18 20 30 35 43 18",
"98403,23751 47 37 44 26 23 17 3 13 48 4 16 42 29",
"32918,74706 17 16 39 47 41 20 23 36 5 35 2 6 43 43",
"9851,96894 8 22 44 36 20 21 5 20 12 9 43 13 46 11",
"86305,55072 37 21 26 29 20 3 20 17 19 46 26 33 31",
"66150,16273 45 13 39 7 21 34 15 11 45 39 15 33 5",
"95275,37494 1 35 32 43 7 0 21 23 5 39 44 21 18 12",
"16184,79884 40 25 39 5 8 2 19 10 47 2 25 29 25 29",
"77000,48925 33 22 36 38 25 37 13 31 40 46 40 36 22",
"19246,92639 10 38 9 28 19 28 28 48 31 27 39 39 3",
"37419,96699 30 26 33 6 9 8 45 26 21 6 20 46 18 43",
"65611,72059 8 30 23 4 44 24 10 13 27 3 32 1 48 48",
"78307,80168 37 7 8 17 0 31 34 41 48 33 33 48 1 48",
"35276,57349 8 32 45 34 30 37 28 42 12 46 16 49 3",
"10106,992 36 25 44 41 1 7 36 13 15 6 6 1 24 49 1",
"43647,68652 21 5 35 44 39 27 41 9 25 16 34 23 11",
"7588,43383 32 33 29 2 17 13 30 38 23 16 25 5 23 0",
"39549,20275 16 13 40 14 32 43 1 1 42 43 42 43",
"49470,43071 25 9 8 12 30 11 44 26 28 27 24 45 4 6"}
45315043
Returns: 1.4635199471353126

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2946

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5856&pm=2946

Writer:

the_one_smiley

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Graph Theory, Math, Search, String Parsing