Superposition

Special Judge Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      Tony is writing financial software. One of the components he is writing now will have to deals with risk and income graphs of various market instruments. Now he needs to plot the graph of a superposition of two continuous piecewise linear functions.
      Tony is given two functions: f (x) and g(x) and needs to find the explicit representation of the function g(f (x)).

Input

      The input file consists of two blocks, one describes f and another describes g. 

      Each blocks starts with l — the number of intervals of linearity of a function (1 ≤ l ≤ 1000, l != 2).
      If l > 2, the following l − 1 lines contain the breaking points of the function. Each line contains two integer numbers: xi, y(i from 1 to l − 1, xi< xi+1). The function a(x) described by the block is defined as follows:

      Here ki= (yi+1 − yi)/(xi+1 − xi).
      If l = 1 the following line contains one integer number y, the function described is a(x) = y.
      All coordinates in the input file do not exceed 10by their absolute values.

Output

      Output the function g(f (x)) in the same format as the functions in the input file. The number of intervals of linearity in the description must be minimal possible. It is guaranteed that the number of intervals of linearity of the resulting function will not exceed 100 000. Output floating point numbers with absolute or relative precision of at least 10-8
.

Sample Input

3
0 0
2 3
4
0 0
1 3
2 0

Sample Output

4
0 0
0.666666666667 3
1.333333333333 0

Source

Andrew Stankevich Contest 23

Manager

Information
Solved Number4
Submit Number18
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel