扫描线
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

现有一凸多边形在二维平面上。一水平直线在无穷远处，每时刻以一个单位长度的速度朝着凸多边形的方向移动。t 时刻与凸多边形相交，经过了 x 个时刻与凸多边形相离。你可以任意旋转或平移这个凸多边形，求这条直线与凸多边形相交的最短时间 x 是多少？

输入描述:

本题包含多组数据
第一行包含一个正整数 T\ (1 \leq T \leq 5 \times 10^5)。
对于每组数据：
第一行包含一个正整数 n\ (3 \leq n \leq 5 \times 10^4)。
接下来 n 行，每行包含两个整数 x,y\ (-10^6 \leq x,y \leq 10^6)，表示凸多边形顶点的坐标，按逆时针顺序给出。
\sum_{i=1}^{T} n \leq 5 \times 10^{5}

输出描述:

对于每组数据：
输出一行包含一个小数 x，表示最短时间（保留两位小数）
示例1

输入

复制 
3
3
-2 0
2 0
0 1
4
2 0
4 2
2 4
0 2
5
0 0
3 1
2 4
-1 5
-2 4

输出

复制 
1.00
2.83
3.58

说明

对于样例一：
无需任何操作

对于样例二：

如下图所示是方案之一：