题目描述

你可能听说过作为千克标准的铂铱圆柱体，但你知道有一条特殊的线段被用作千米的标准吗？它位于二维平面中的 $(0, 0)$ 到 $(0, 1000)$，地点保密且非常平坦。

自然，这条线段极其珍贵，因此由 $N$ 台旋转监控激光器保护。每台激光器在二维平面中是一条射线，拥有一个固定端点，并以每秒 1 圈的速度围绕该端点旋转。每台激光器是顺时针还是逆时针旋转，由安保系统独立且等概率地随机选择。

激光不会被其他激光、端点或线段本身阻挡。没有任何激光的端点在该线段上。

你被雇佣来审计安保系统，但你只能获得某一时刻的快照，快照显示了每台激光器的端点和当时的朝向。由于这只是一个快照，你无法推断激光器的旋转方向。

你已经确定，如果存在某个非空的时间开区间，在此期间没有任何激光器照射到该线段，则该线段有可能被盗。请问这种情况发生的概率是多少？

输入格式

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为一个整数 $N$，表示激光器的数量。接下来的 $N$ 行，每行包含四个整数 $X_i$、$Y_i$、$X_i'$、$Y_i'$，表示第 $i$ 台激光器的端点坐标和射线上另一点的坐标。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是所求概率。$y$ 的绝对误差或相对误差在 $10^{-6}$ 以内均视为正确。

输入输出样例 #1

输入 #1

3
5
0 1001 -1 1001
0 1001 -1 1001
0 1001 -2 1001
0 1001 0 500
0 1002 1234 5678
4
500 500 1000 1000
500 500 0 1000
500 500 0 0
500 500 1000 0
4
500 500 1000 1001
500 500 0 1000
500 500 0 0
500 500 1000 0

输出 #1

Case #1: 1.000000
Case #2: 0.750000
Case #3: 1.000000

说明/提示

样例解释

在样例 1 中，注意多台激光器可能有相同的端点和初始朝向，但这并不意味着它们的旋转方向相同。（还要注意，第二台和第三台激光器虽然输入不同，但初始朝向相同。）无论旋转方向如何，每台激光器仅在指向负 $y$ 方向时才能照射到线段，因此显然总有一段时间没有激光器照射到线段，答案为 1。

在样例 2 中，每台激光器在旋转周期的 $1/4$ 时间内照射到线段。只有当第 1 和第 4 台激光器旋转方向相同，且第 2 和第 3 台激光器旋转方向相同时，线段才会始终被激光照射。该概率为 $1/4$，所以答案为 $3/4$。

样例 3 与样例 2 类似，但有细微差别，保证即使所有激光器旋转方向相同，也会有某一时刻没有激光器照射到线段，因此答案为 1。

数据范围

• $1 \leq T \leq 100$。
• $-10^6 \leq X_i \leq 10^6$，对所有 $i$。
• $-10^6 \leq Y_i \leq 10^6$，对所有 $i$。
• $-10^6 \leq X_i' \leq 10^6$，对所有 $i$。
• $-10^6 \leq Y_i' \leq 10^6$，对所有 $i$。
• $(X_i, Y_i) \neq (X_i', Y_i')$，对所有 $i$。
• 如果 $X_i = 0$，则 $Y_i < 0$ 或 $Y_i > 1000$，对所有 $i$。（没有激光器的端点在该线段上。）

测试点 1（10 分，公开）

• $1 \leq N \leq 10$。

测试点 2（38 分，隐藏）

• $1 \leq N \leq 10000$。
• 其中 $N > 100$ 的测试用例不超过 8 个。