题目描述

给定平面上的 $N$ 个点（称为初始点），可能存在多种方式对它们的凸包进行三角剖分。这里的凸包是指包含所有点的最小凸多边形，且所有点要么在边界上，要么在内部。三角剖分需满足以下条件：

1. 顶点限制：三角形的顶点必须是初始点。
2. 边限制：三角形的边上（不包括顶点）不能有其他初始点。
3. 无重叠：所有三角形的面积之和等于凸包的面积。

下图是一个凸包三角剖分的示例：

可以知道，凸包的三角剖分方式可能有很多种，但剖分后的三角形数量 $M$ 是固定的（$M = N - 2$）。每个三角剖分会生成 $3M$ 个角（因为每个三角形有 $3$ 个角）。你的任务是找到一种三角剖分，使得其所有角中的最小角尽可能大（即比其他剖分方式的最小角更大）。

假设：

• 所有点不共线。
• 任意两点不重合。

输入格式

• 输入包含多个测试用例。
• 每个用例的第一行是整数 $N$（$3 \leq N \leq 100$）。
• 接下来 $N$ 行，每行两个整数 $X_i$ 和 $Y_i$（$0 \leq X_i, Y_i < 100$），表示一个初始点的坐标。

输出格式

• 对于每个用例，输出一个浮点数，保留两位小数，表示所求三角剖分的最小角度值。

示例输入 1

9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
3
1 1
1 0
0 1
4
0 0
5 1
0 1
1 2

示例输出 1

45.00
45.00
18.43

题目来源

POJ Monthly, kicc