问题描述

在多边形王国（Polygonia），王室成员包括国王、王后以及10岁的双胞胎王子：钝角王子（Prince Obtuse）和三等分王子（Prince Trisect）。这对双胞胎竞争激烈，每年生日分蛋糕时，他们总是为了谁能得到更大的一块而争吵不休。聪明的国王和王后设计了一种方法来防止这种争吵：其中一位王子可以将蛋糕切成两块，然后另一位王子可以选择他想要的那块。

多边形王国的蛋糕总是凸四边形（四个边的多边形，每个内角都小于180度）。此外，当地习俗规定，所有的切蛋糕方式都必须是直线切割，这条直线可以连接两个顶点、两条边的中点，或者一个顶点和一条边的中点。例如，下图展示了一个典型蛋糕的所有合法切割方式。

你的任务是为多个不同的蛋糕确定最佳切割方式，即能将蛋糕分成两块，使这两块面积（忽略蛋糕厚度）尽可能接近的切割方式。例如，给定一个蛋糕，其顶点（从上方看时）按逆时针顺序位于点(0, 1)、(6, 0)、(5, 2)和(2, 3)，最佳切割方式将蛋糕分成两块，一块面积为4.375，另一块面积为5.125；这条切割线连接点(1, 2)和(5.5, 1)（两条边的中点）。

输入

输入由一系列测试用例组成，每个测试用例包含四个(x, y)值，表示从蛋糕正上方看时，蛋糕顶点的逆时针遍历顺序；最后一个测试用例后面跟着一行包含八个零的行。不会有三个点共线，所有四边形都是凸四边形，并且所有坐标的绝对值都不超过10000。

输出

对于每个蛋糕，输出蛋糕编号，后跟两个面积值，按从小到大的顺序排列，精确到三位小数。

输入示例

0 1 6 0 5 2 2 3
0 0 100 0 100 100 0 100
0 0 0 0 0 0 0 0

输出示例

Cake 1: 4.375 5.125
Cake 2: 5000.000 5000.000

来源

2003年北美中部东部区域赛