Description

某片森林中有 $N$ 棵树，每棵树上都住着一只松鼠。

森林的边界是指包含所有树的最小面积凸多边形，就像用一根巨大的橡皮筋把整个森林包裹起来一样。

形式化地说，每棵树在二维平面上是一个唯一坐标为 $(X_i, Y_i)$ 的点，边界就是这些点的凸包。

有些树在森林的边界上，也就是说它们位于凸多边形的边或顶点上。松鼠们想知道它们的树距离成为森林边界上的树还有多远。

每次，一只松鼠会从它的树上下来，观察整个森林，并确定至少需要砍掉多少棵树，才能让它自己的树处于森林的边界上。然后它会把这个数字记在一根木头上。

请你求出所有松鼠记下的数字列表。

Input Format

输入的第一行是测试用例的数量 $T$。接下来有 $T$ 组测试数据；每组测试数据第一行为一个整数 $N$，表示树的数量，接下来的 $N$ 行，每行包含两个用空格分隔的整数 $X_i$ 和 $Y_i$，表示每棵树的坐标。任意两棵树的坐标都不相同。

Output Format

对于每组测试数据，输出一行 "Case #$x$:"，接下来输出 $N$ 行，每行一个整数，第 $i$ 行表示住在第 $i$ 棵树上的松鼠需要砍掉多少棵树，才能让它的树处于边界上。

2
5
0 0
10 0
10 10
0 10
5 5
9
0 0
5 0
10 0
0 5
5 5
10 5
0 10
5 10
10 10

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

Hint

样例解释

在第一个样例中，有四棵树形成一个正方形，第五棵树在正方形内部。前四棵树已经在边界上，所以这些松鼠都写下 $0$。第五棵树需要砍掉一棵树才能在边界上，所以第五只松鼠写下 $1$。

数据范围

• $-10^6 \leq X_i, Y_i \leq 10^6$。

小数据范围

• 时间限制：5 秒。
• $1 \leq T \leq 100$。
• $1 \leq N \leq 15$。

大数据范围

• 时间限制：20 秒。
• $1 \leq T \leq 14$。
• $1 \leq N \leq 3000$。

由 ChatGPT 4.1 翻译