6493: BZOJ2493:Share the Cakes
Description
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.
输入格式
输出格式
样例输入
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
样例输出
Case #1: 0 1 Case #2: 1 0
提示
没有写明提示
题目来源
Acm 2011 上海