CAKE4 - Share the Cakes

no tags 

Lunar Rose is a pure and kind girl who was born in a serene town on, with surprising coincidence, the Mid-autumn Festival that year. Therefore, on each of her birthday, she enjoys two cakes: for the birthday, and for the festival.

This year, Lunar would like to share the cakes with Jaddy, her boyfriend, on the nice day, isn't it so romantic? What is the tragedy, Jaddy screwed up, again:

When Lunar placed two cakes on the table, she wanted Jaddy to cut the cakes for her so that they can both have half of the moon cake and so do the birthday cake. But Jaddy, as a lazy and impetuous guy, he just used a knife to cut them together easily, hence although the two cakes had been cut into two pieces each, they were not really uniform. What was worth? Lunar is a pretty perfectionist and suddenly quite angry with Jaddy due to his arbitrariness. Finally, Lunar chose to leave him. Stupid Jaddy!

Jaddy became extremely regretful and distressing. Lunar, a softhearted girl, does not have the heart to make him so painful so that she'd like to give Jaddy a chance to do it again. However, she set a strict limit for this task: Jaddy can only use one cut to separate the two cakes into equivalent halves. Evil Ms. Rose!

Both two cakes are convex polygons; the table and knife are both big enough and long enough thus can be considered as infinite planar and line. This way, tell Jaddy a strategy, which means a line, satisfying Lunar's condition to cut cakes so that he can get her back.

Input

The first line of the input data is a positive integer T (T <= 100) indicating the number of test cases. Then T cases follow. Each test case contains description of two cakes (polygons): each polygon begins with an integer n which denotes the number of vertices, and then n pairs of integers (x, y) follows describing the coordinates of vertices in clockwise or counterclockwise order. You may assume that each polygon has no more than 20 vertices and all the coordinates are in range of [-1000, 1000]. Besides, no point is in the two polygons (including their boudary) simultaneously.

Output

For each test case, output two real numbers k and b, leading by the case number, which means that Jaddy should cut the cakes along the line y=k*x+b. It is guaranteed that both k and b among the answers are in range of [-10000, 10000]. See sample output for further details.

We accept answers within 10-4 relative or absolute error.

Example

Input:
2
3
0 0
1 1
0 2
3
2 1
3 0
3 2
4
0 0
1 0
1 1
0 1
4
2 2
3 2
3 3
2 3

Output:
Case #1: 0 1
Case #2: 1 0

This problem is first (and only) solved by team Y.E.S (Tsinghua University) at 201 minutes after the onsite contest starts. (They have 1 wrong try before they get Accepted.)

 


hide comments
[Rampage] Blue.Mary: 2011-11-11 03:02:00

I know that. I'll contact the original problem setter to solve your problem ASAP.

Edit: I think your solution is not precise enough. The difference between the areas of the two halves your line cut out is about 2e-4 on test case #5, which is bigger than EPS defined in problem statement. "To watch the first channel in the sequence, you must press the digits of the channel." In this sentence, "sequence" just means "the sequence given in the input file", not "your input sequence".

Last edit: 2023-12-22 02:37:43
Arbi Zadoori: 2011-11-05 09:26:52

i meant bigger EPS (10^(-7)) not smaller EPS :-)

Arbi Zadoori: 2011-11-05 09:24:48

Hi, I think the test special judge is not smart enough :-D I checked my output with the judges input and the answers were the same with relative error of 10^(-4). except in the case#5 where my program prints (481.136491791 , -240.568245896) and the judge output says (481.135620001 , -240.567630151). I got suspicious and checked both lines to see if the line that my program chooses is correct enough and guess what!!! my chosen line divides both polygons with an EPS of about 10^(-12) and the judge's line divides it with a much smaller EPS (about 10^(-7)). The special judge configuration should be definitely revised.


Added by:Fudan University Problem Setters
Date:2011-10-10
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM/ICPC Regional Contest, Shanghai 2011; Problem Setter: lcosvse