P13217 [GCJ 2015 #1A] Logging

某片森林中有 $N$ 棵树，每棵树上都住着一只松鼠。 森林的**边界**是指包含所有树的最小面积凸多边形，就像用一根巨大的橡皮筋把整个森林包裹起来一样。 形式化地说，每棵树在二维平面上是一个唯一坐标为 $(X_i, Y_i)$ 的点，边界就是这些点的凸包。 有些树**在森林的边界上**，也就是说它们位于凸多边形的边或顶点上。松鼠们想知道它们的树距离成为森林边界上的树还有多远。 每次，一只松鼠会从它的树上下来，观察整个森林，并确定至少需要砍掉多少棵树，才能让它自己的树处于森林的边界上。然后它会把这个数字记在一根木头上。 请你求出所有松鼠记下的数字列表。

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

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

**样例解释** 在第一个样例中，有四棵树形成一个正方形，第五棵树在正方形内部。前四棵树已经在边界上，所以这些松鼠都写下 $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 翻译