Bridge builders need your help for static load testing!
(The most famous early cantilever bridge is the Forth Rail Bridge, built in 1890. This bridge held the record for longest span in the world for seventeen years. The structural principles of the suspended span cantilever are illustrated in the photo.)
Given a grid structure built of joints and rods of different strength, you need to determine how to distribute a predefined amount of load among the joints in a way that the structure does not break. To simplify the problem, we assume the following restrictions:
Wrong input | Correct input |
---|---|
![]() |
![]() |
Wrong input | Correct inputs | |
---|---|---|
![]() |
![]() |
![]() |
Note: you can request trace for this problem for -5 points. The trace output would contain a short hint about how the solution failed.
Each line of the input contains three numbers.
The first line contains the number of joints (NJ), the number of rods (NR) and the load (L) which should be distributed among the joints.
The next NJ lines describe the joints. A line contains the x, y coordinates of a joint and the maximum amount of load it can take.
The remaining NR lines describe the rods. A line contains the indices of the two joints connected and the maximum force the rod can take (either push or pull force, the joints are indexed from 1 in the order they appear in the list)
The first two joints are the two fixed joints which can take arbitrary amount of force.
The output should have NJ lines containing the amount of load placed at the joints in the order the joints were given. (Loads are always non-negative.)
The sum of the loads should give L and the absolute value of the forces in each rod should be less than or equal to the given maximum.
Each input can be solved. The loads and coordinates are real numbers. We will check the results with 0.001 tolerance, so a rod will break if according to our calculations the force in it is less than the maximum allowed force + 0.001.
5 6 3 1 0 0 3 0 0.2 0 1 1.5 2 1 1.5 4 1 1.5 1 3 1 1 4 1 2 4 1 2 5 1 3 4 1 4 5 1
0 0.2 0.7 1.4 0.7