问题陈述
有一座城市,其形状为 $1{,}000 \times 1{,}000$ 正方形。 城内有一条大河,自北向南流淌,将城分为东西两部分。
最近,市长决定修建一条从西部$s$点到东部$t$点的高速公路。 一条高速公路由河上的一座桥和两条道路组成:其中一条道路连接 $s$ 和桥梁的西端,另一条道路连接 $t$ 和桥梁的东端。 请注意,每条道路不必都是直线,但与河流的交叉长度必须为零。
为了削减建筑成本,市长打算修建一条满足以下条件的高速公路:
- 由于桥梁的成本比道路高,因此首先连接东西部分的桥梁长度必须尽可能短。
- 在上述条件下,两条道路的长度之和最小。
你的任务是编写一个程序,计算满足上述条件的高速公路的总长度。
输入
输入由单个测试用例组成。测试用例的格式如下。
$sx$ $sy$ $tx$ $ty$
$N$
$wx_1$ $wy_1$
:
:
$wx_N$ $wy_N$
$M$
$ex_1$ $ey_1$
:
:
$ex_M$ $ey_M$
首先,我们用坐标$(x, y)$来引用城市上的一个点:到西边的距离是$x$,到北边的距离是$y$。
第一行包含四个整数 $sx$、$sy$、$tx$ 和 $ty$ ($0 \leq sx, sy, tx, ty \leq 1{,}000$):点 $s$ 和 $t$ 分别位于 $(sx, sy)$ 和 $(tx, ty)$。 下一行包含一个整数 $N$ ($2 \leq N \leq 20$),其中 $N$ 是组成西河边的点的数量。 以下$N$行中每行包含两个整数$wx_i$和$wy_i$($0 \leq wx_i, wy_i \leq 1{,}000$):西河边第$i$点的坐标为$(wx_i, wy_i)$。 西河边是对所有$1 \leq i \leq N-1$ 连接$(wx_i, wy_i)$ 和$(wx_{i+1}, wy_{i+1})$ 之间的线段得到的折线。 下一行包含一个整数 $M$ ($2 \leq M \leq 20$),其中 $M$ 是构成东河边的点数。 以下$M$行中每行包含两个整数$ex_i$和$ey_i$($0 \leq ex_i, ey_i \leq 1{,}000$):东河边第$i$点的坐标为$(ex_i, ey_i)$。 东河边是对所有$1 \leq i \leq M-1$ 连接$(ex_i, ey_i)$ 和$(ex_{i+1}, ey_{i+1})$ 之间的线段得到的折线。
您可以假设测试用例处于以下条件下。
- $wy_1$ 和 $ey_1$ 必须为 0,$wy_N$ 和 $ey_M$ 必须为 $1{,}000$。
- 每条折线都没有自交点。
- 代表西河边和东河边的两条折线没有交叉点。
- 点 $s$ 必须位于城市的西部。更准确地说,$s$必须位于城市的正方形边和西河边折线所围成的区域上,并且不包含东河边点。
- 点 $t$ 必须位于城市的东部。更准确地说,$t$必须位于城市的正方形边和东河边折线所围成的区域上,并且不包含西河边点。
- 每条折线仅在两个端点处与正方形相交。换句话说,$0 < wx_i, wy_i <1{,}000$ 对于 $2 \leq i \leq N-1$ 成立,$0 < ex_i, ey_i <1{,}000$ 对于 $2 \leq i \leq M-1$ 成立。
输出
输出单行空格分隔的两个数字:满足上述市长要求的桥梁长度和高速公路总长度(即桥梁和两条道路)。 输出可以包含不超过 $10^{-8}$ 的绝对或相对误差。
示例输入 1
200 500 800 500 3 400 0 450 500 400 1000 3 600 0 550 500 600 1000
样本输入 1 的输出
100 600
示例输入 2
300 300 700 100 5 300 0 400 100 300 200 400 300 400 1000 4 700 0 600 100 700 200 700 1000
样本输入 2 的输出
200 541.421356237
示例输入 3
300 400 700 600 2 400 0 400 1000 2 600 0 600 1000
样本输入 3 的输出
200 482.842712475
示例输入 4
200 500 800 500 3 400 0 450 500 400 1000 5 600 0 550 500 600 100 650 500 600 1000
样本输入 4 的输出
100 1200.326482915