Share the Cakes

时间限制：5s 空间限制：128MB

题目描述

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.

输入格式

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 counterclockwise. You may assume that each polygon has no more than 20 vertices and all the coordinates are in range of [-1000, 1000]. Besides, the two polygons can be separated by a line, without touching on any points of the line.

输出格式

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. Any answer with 10^-4 relative or absolute error is acceptable.

样例输入

样例输出

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

提示

没有写明提示

题目来源

Acm 2011 上海