题目描述

身为怪盗团的一员，你已经拿到了豪华美术馆的秘宝，现在你想找到伙伴会合。

你位于一个布满红外线装置的美术馆中。房间内有 $n$ 个互不相同的红外线装置点（大小可忽略），其中任意两个装置点之间会形成红外线。若你的路径穿过红外线（即从线段一侧跨越至另一侧），则会被检测到。但是你可以穿过装置点（甚至接触装置点），这不会触发红外线。

你的初始位置是点 $S(x_S, y_S)$，目标位置是点 $E(x_E, y_E)$。已知 $S$ 和 $E$ 不被任意三个装置构成的三角形包含（在内部或边上）。求从 $S$ 到 $E$ 不被发现的最短路径长度。

输入格式

每个测试文件包含多组测试数据。第一行包含测试数据的组数 $T$ ($1≤T≤10^3$）。每组测试数据的格式如下。

每组测试数据的第一行包含四个整数 $x_S,\ y_S,\ x_E,\ y_E$ ($\left|x_S\right|,\left|y_S\right|,\left|x_E\right|,\left|y_E\right|≤10^9$)，表示 $S$ 点和 $E$ 点位置。

第二行包含一个整数 $n$ ($1≤n≤10^5$)，表示红外线装置点的数量。

接下来 $n$ 行，每行两个整数 $x_i$ 和 $y_i$ ($\left|x_i\right|,\left|y_i\right|≤10^9$)，表示一个红外线装置的位置。保证任意两个装置点的坐标互不相同，且不位于 $S$ 点或 $E$ 点。

在每个测试文件内，保证所有测试数据的 $n$ 之和不超过 $2×10^5$ 。

输出格式

对于每组数据，输出一行一个小数，表示 $S$ 点达到 $E$ 点路径的最小值。

当你的输出与标准答案的绝对误差或相对误差不超 $10^{-6}$ 时，你的输出将会被判定为正确。

具体地说，令你的答案为 $a$ ，标准答案为 $b$ 。你的答案被认为是正确的当且仅当 $\frac{\left|a-b\right|}{max{(1,\left|b\right|)}}\le10^{-6}$ 。

2
0 0 0 2
3
1 0
2 0
1 1
3 -1 0 2
3
1 0
2 0
1 1

2.0000000000
4.2426406871