Share the Cakes#3092
Lunar Rose is a pure and kind girl who was born in a peaceful town and, coincidentally, on the Mid-Autumn Festival that year. Therefore, on each of her birthdays, she enjoys two cakes: one for her birthday and one for the festival.
This year, Lunar wants to share the cakes with Jaddy, her boyfriend, on this nice day—isn't it romantic? Unfortunately, Jaddy ruined it again:
When Lunar placed the two cakes on the table, she asked Jaddy to cut them so that each could have half of the moon cake and half of the birthday cake. However, Jaddy, being lazy and careless, just took a knife and cut them together without much thinking. As a result, although both cakes were cut into two pieces, the pieces were not equal. Worse, Lunar, being a perfectionist, got very angry with Jaddy for his carelessness and decided to leave him. Poor Jaddy!
Jaddy felt deep regret and sadness. Lunar, being soft-hearted, did not want to see him so upset and decided to give him another chance. However, she set a strict requirement: Jaddy can only use one cut to split both cakes into equal halves. Strict Miss Rose!
Both cakes are convex polygons; the table and knife are large and long enough so that they can be considered as an infinite plane and a line. Your task is to help Jaddy find a strategy—a line—that satisfies Lunar's requirement to cut the cakes, so he can win her back.
The first line of the input contains a positive integer (T \leq 100), the number of test cases. Then test cases follow. Each test case describes two cakes (polygons): each polygon starts with an integer , the number of vertices, followed by pairs of integers describing the coordinates of the vertices in counterclockwise order. You may assume that each polygon has at most vertices and all coordinates are in the range . Furthermore, the two polygons can be separated by a line without touching any points on the line.
For each test case, output two real numbers and , starting with the case number, which means Jaddy should cut the cakes along the line y = kx + b. It is guaranteed that both and in all answers are in the range . See sample output for further details. Any answer with relative or absolute error of 10^{-4} is acceptable.
Example 1