I. Abstract
In the place and route (P&R) flow, a router might still leave some nets open after routing is done. These opens are usually caused by ECO (Engineering Change Order) or some user changed design. Thus it is very helpful to have an automatic tool to detect if a net is still open after routing. Also, a tool should indicate the (shortest) paths to reconnect existing net shapes to resolve the open. Furthermore, the indicated paths must be obstacleaware for that a path overlap with obstacles is not legitimate in a real case.
II. Problem Description
 This problem focuses on a single net with large scattered routed net shapes. The contestants are requested to generate paths to connect all these routed net shapes and vias while having minimum line length/via cost.
 Given a set of routed net shapes $R = \{R_1,R_2,…,R_j\}$, a set of routed net vias $V = \{v_1,v_2,…,v_k\}$, a set of obstacles $O = \{O_1,O_2,…,O_m\}$ on routing layers $L = \{M_1,V_1,M_2,V_2,…,V_{n1},M_n\}$, with a design boundary $B$, spacing $S$ and via cost $C_v$
 Contestants are requested to find a set of paths $p = \{p_1, p_2,…,p_l\}$ to connect all routed net shapes $R$ and routed net vias $V$ together.
 Each path $p_i$ can be an Hline, a Vline or a via. Steiner points are allowed.
 Examples:
 As shown in Figure 1, the blue rectangles are the routed net shapes $R$ of a net containing some opens. Your goal is to output a set of paths to connect the existing net shapes to form a single connected component.
 The path set $p$ consists of red lines and orange vias. The path set in this figure is one of the valid outputs that contestants could generate.
 The gray rectangles are the obstacles $O$. The paths (line/via) should always keep a minimum spacing $S$ to these obstacles.
 The outmost rectangle is the design boundary $B$. The paths (line/via) should always keep a minimum spacing $S$ to it as well.
 Detailed Rules:
 Format of Shapes/Lines/Vias
 A point in this problem is expressed as a pair of nonnegative integers.
 Points have no area and lines have no width (more explanations later).
 The routed net shapes $R$, obstacles $O$ and design boundary $B$ are always rectangles represented by their upper right (UR) and lower left (LL) corners.
 The routed net vias $V$ and your output vias are always points.
 Your output lines must be horizontal(yequal) or vertical(xequal) lines.
 Format of Metal/Via Layers
 Layers are stacked like those shown in Figure 2.
 All layers are aligned with the same coordinate system in the x and y axes.
 All the routed net shapes $R$ and obstacles $O$ and lines exist only on metal layers.
 A via on layer $V_{i1}$ connects the same point of $M_{i1}$ and $M_i$.
 Definition of Connection


Figure3a. Lines connecting net shapes 
Figure3b. Lines not connecting net shapes 
 Any point touching between line/via/netShapes counts the connection.
 For Figure 3b, these two lines do not connect the existing net shapes because the end points of the lines are not on the routed net shapes.
 Stacked via is also considered as connected.
 Steiner point identification


Figure4a. Lines and vias not conntected 
Figure4b. Lines and vias conntected 
 You should identify the location of Steiner point. For lines and vias, we only check if the end points are touched, as shown in Figure 4.
 Spacing to Obstacles and Boundaries
Figure5. valid path.
 As mentioned, a line in this problem has no width. So the path in Figure 5 is valid.
 You only need to consider the spacing to obstacles and boundaries because all routed net shapes and via are for the same net.
 The given routed net shapes/via will always keep a minimum spacing S to these obstacles and boundaries.
 Multithreading Allowed and Encouraged.
 The maximum number of cores that can be used is 4.
III. Evaluation Methodology
 Overall $Cost=\sum\limits_{q=1}^t=Cost(p_q)+Disjoint \ cost$
 If $p_q$ is a Hline or Vline, Cost($p_q$) = length of this Hline or Vline.
 If $p_q$ is a via, Cost($p_q$) = $C_v$.
 The goal is to minimize the overall cost for each case.
 There are several things to notice:
 If the components are not connected as a single net:
$Disjoint\ cost = 2 \times (\#components  1) \times (boundary\Delta X + boundary\Delta Y + \#ViaLayers \times C_v)$
($boundary\Delta X = UR_xLL_x\ of\ B, boundary\Delta Y = UR_yLL_y\ of\ B,\ and\ \#ViaLayers=\#MetalLayers1$)
 Invalid paths would be discarded as shown Figure 6.
Figure6. Invalid paths
 Runtime bonus/penalty to overall cost
Figure8. Runtime bonus calculation
 We measure the runtime by the clock on the wall time.
 If your runtime is within (or equal to) the first quartile of all the runtime of the teams. Then there will be a bonus 10% off to your overall cost, as shown in Figure 8.
 If your runtime is within (or equal to) the second quartile of all the runtime of the teams. Then there will be a bonus 5% off to your overall cost.
 If your runtime is over 4hrs, then the output of that case will be discarded. The cost would be treated as though the net is disjoint (huge disjoint cost).
IV. Example
 Remember that Line Cost = length
 Input format:
ViaCost = Cv
Spacing = S
Boundary = (LLx,LLy) (URx,URy)
#MetalLayers = W
#RoutedShapes = X
#RoutedVias = Y
#Obstacles = Z
RoutedShape Layer (LLx,LLy) (URx,URy)
…
RoutedVia Layer (x,y)
…
Obstacle Layer (LLx,LLy) (URx,URy)
 You can output Hline/Vline/via in any order. But be careful about IO handling in multithread environment.
 Output Format:
Hline Layer (x1,y) (x2,y)
…
Vline Layer (x,y1) (x,y2)
…
Via Layer (x,y)
 Take Figure 1 for example, the input will be:
ViaCost = 20
Spacing = 5
Boundary = (0,0) (1000,1000)
#MetalLayers = 2
#RoutedShapes = 7
#RoutedVias = 1
#Obstacles = 3
RoutedShape M1 (50,100) (250,150)
RoutedShape M1 (600,20) (750,140)
RoutedShape M1 (50,850) (250,900)
RoutedShape M1 (10,800) (500,995)
RoutedShape M2 (75,20) (200,750)
RoutedShape M2 (375,100) (575,600)
RoutedShape M2 (475,20) (670,450)
RoutedVia V1 (175,125)
Obstacle M1 (350,300) (650,750)
Obstacle M1 (50,350) (650,650)
Obstacle M2 (350,700) (950,800)

Example output:
Vline M1 (700,140) (700,550)
Hline M2 (575,550) (700,550)
Hline M1 (500,850) (700,850)
Via V1 (700,550)
Vline M1 (700,550) (700,850)
Hline M2 (200,150) (375,150)
 Your program should be named net_open_finder and we can execute as follows:
./net_open_finder <input.txt> <output.txt>
V. Test Cases and Evaluator