屋顶 Roof
题意翻译
你要建一座新房子。为了了解屋顶的最低建筑成本，你想知道它的高度。但是你只知道屋顶边界形状，所以你要根据边界信息计算屋顶的高度。正式描述如下。房屋的边界被定义为一个直多边形，只有与XY坐标轴平行的边。设P是具有n个顶点的直多边形。直骨架SK（P）是当P收缩时，P的顶点移动时的两面夹线；当P收缩时，每个边以相同的速度向内收缩和向上抬高。图1(参见原题)（a）和（b）表示了P和SK（P）的收缩过程。
现在我们假设P在XY平面上，并且P以单位速度向内收缩和向上移动（+Z方向）。P的边界轨迹形成一个三维多面体表面，称为地形，SK（P）可以看作是该边缘在XY平面上的投影。该地形的每个面都位于与XY平面成二面角45°的平面内。这个地形的每个面都与P的至少一个边界连接。我们把这个地形叫做多边形P对应的的屋顶。屋顶的高度是屋顶上最高点的高度。你的任务是计算输入的直多边形P形成的屋顶高度。
### 输入
程序从stdin读取输入。输入由T个测试数据组成。测试数据T的个数在输入的第一行给出。每个测试数据都以一个整数n，即多边形P的顶点数开头，（4≤n≤1,000）。在下一行中，以逆时针顺序给出P的n个顶点的坐标。每一对整数分别是P的一个顶点的x和y坐标。坐标由单个空格分隔，范围[1,100000]
### 输出
程序写入stdout。每个测试数据为一行，保留一位小数。
#### Sample Input
```
3
4
1 1 4 1 4 4 1 4
6
4 1 8 1 8 6 1 6 1 4 4 4
14
1 1 4 1 4 2 7 2 7 1 11 1 11 10 8 10 8 8
1 8 1 6 3 6 3 4 1 4
```
#### Sample Output
```
1.5
2.0
3.0
```
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4563
[PDF](https://uva.onlinejudge.org/external/16/p1688.pdf)