提示: 欢迎访问OurACM平台。
Problem 1904 Cake,Cake,Delicious

Accept: 33    Submit: 75
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Oh my god! The Cake above must be delicious! Chjing takes this and shares it with us! But there are too many people, so chjing cuts the cake. Now we know all the cutting, chjing wants to know the maximal volume of cake he may gets after all the cutting.

Here one cutting is described as two points on a line, chjing will cut along the described line.

To make the task more easy, the height of the cake is always 1, and the length of side of the “square” cake is 100, and you may consider it in the following coordinate system:

Input

In the first line there is an integer T indicates the number of test cases.(1 <= T <= 10)

Then follows T cases.

In every case, the first line is an integer N indicate the number of “cutting” . ( 0 <= N <= 10)

Then follows N lines, every line has four integers : X0 Y0 X1 Y1 indicate the two different points on the “cutting” line. (0 <= X0,Y0,X1,Y1 <= 1000)

Output

Output one line.

First output “Case #idx: ”, here idx is the case number count from 1.

Then output the answer rounded to 3 digits after the decimal point..

Sample Input

2 0 2 0 5 100 5 0 0 1 1

Sample Output

Case #1: 10000.000 Case #2: 4987.500

Hint

In case 2, the cake was cut as the following figure.

Source

FOJ有奖月赛-2010年05月

Submit  Back  Status  Discuss