11494번 - Equilibrium State 스페셜 저지다국어채점 준비 중

When the sum of forces exerted on an object, say P, is 0 as shown in Figure 1, the object will not move. It is said that the object is in an equilibrium state.

Figure 1. Forces exerted on object P

Suppose a situation as shown in Figure 2. There are two fixed points F₁ and F₂ on the x-axis. Object P is connected by two springs S₁ and S₂. Spring S₁ connects F₁ and P and spring S₂ connects F₂ and P. Let’s denote w₁ and w₂ to be the elastic coefficients of springs S₁ and S₂, respectively, which denote how stiff the springs are. Let’s also denote x(F₁) and x(F₂) to be the x-coordinates of F₁ and F₂, respectively. Then the force exerted on P by S₁ is w₁ × (x(P) − x(F₁)) by Hooke’s rule, where x(P) is the x-coordinate of P. Similarly, the force exerted on P by S₂ is w₂ × (x(P) − x(F₂)).

Figure 2. An example to illustrate an equilibrium state

For example, in a situation as shown in Figure 2, if x(F₁) = 0, x(F₂) = 7, w₁ = 3, w₂ = 4, and P is in an equilibrium state, then we can determine the location of P, i.e., x(P) = 4.

Consider a similar situation where several objects are connected by multiple springs in a two-dimensional plane as shown in Figure 3. Assume there are k fixed points F₁, … , F_k and m objects S₁, … , S_m. Also, assume there are 5 springs w₁, … , w_m with elastic coefficients w₁, …, w_m, respectively. Each of the springs is used to connect either a fixed point and an object or two objects. If every object is connected to at least two springs, then all the objects will finally get into an equilibrium state. Once all the objects get into an equilibrium state, we can determine the location of every object in the plane.

You are asked to make a program to determine the locations of 6 objects in an equilibrium state using given information: the locations of k fixed points, the elastic coefficients of m springs, and the interconnection information between objects and fixed points.

Figure 3. Another example to illustrate an equilibrium state in the plane

You can assume:

1. All objects are connected to at least two springs and any pair of objects and fixed points are connected through one or more springs. 
2. There is at most one spring between either a pair of (object, object) or a pair of (object, fixed point). 
3. There are at least three non-collinear fixed points. 
4. When all objects are in an equilibrium state, no two springs will cross each other and no two objects will locate at the same position.
5. No two fixed points have the same coordinates.

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing three integers,  k (3 ≤ k ≤ 100), m (3 ≤ m ≤ 3,000), and n (1 ≤ n ≤ 1,000), where k is the number of fixed points, m is the number of springs, n is the number of objects. In the following k lines, each line contains the integer coordinate (x_i, y_i) (−10,000 ≤ x_i, y_i≤ 10,000) of fixed point F_i (1 ≤ i ≤ k). In the following m lines, each line contains three integers w_i, u_i, and v_i (1 ≤ i ≤ m), where w_i (1 ≤ w_i ≤ 100) is the elastic coefficient of spring S_i, and u_i and v_i are the indices of either a fixed point or objects which are connected to spring S_i. If u_i is negative then it means that fixed point F_-ui (1 ≤ −u_i ≤ k) is connected to spring S_i. On the other hand, if u_i is positive then it means that object P_ui (1 ≤ u_i ≤ n) is connected to spring S_i. Similarity holds for v_i.

Your program is to write to standard output. For each test case, print first “Test case number : ” followed by the test case number as shown in the following sample. Then print number i (1 ≤ i ≤ n) starting from 1 to n followed by the coordinate (x_i, y_i) of object P_i in each of the following n lines. You print the coordinates of object P_i with two digits after decimal point after rounding off from the third digit. Three numbers (i, x_i, y_i) in each line should be separated by a blank. If each value of the coordinate is within an error range, 0.01, it will be considered correct.