问题描述

有一个形状为 $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)$。西岸是通过连接 $(wx\_i, wy\_i)$ 和 $(wx\_{i+1}, wy\_{i+1})$ 所有 $1 \leq i \leq N-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)$。东岸是通过连接 $(ex\_i, ey\_i)$ 和 $(ex\_{i+1}, ey\_{i+1})$ 所有 $1 \leq i \leq M-1$ 的线段得到的折线。

可以假设测试用例满足以下条件。

• $wy\_1$ 和 $ey\_1$ 必须为 0，$wy\_N$ 和 $ey\_M$ 必须为 $1{,}000$。
• 每条折线没有自交。
• 表示西岸和东岸的折线没有交点。
• 点 $s$ 必须在城市的西部。更准确地说，$s$ 必须位于城市的正方形边界和西岸折线围成的区域内，不包含东岸的点。
• 点 $t$ 必须在城市的东部。更准确地说，$t$ 必须位于城市的正方形边界和东岸折线围成的区域内，不包含西岸的点。
• 每条折线只在边界的两个端点处与正方形相交。换句话说，对于 $2 \leq i \leq N-1$，$0 < wx\_i, wy\_i <1{,}000$ 和 $2 \leq i \leq M-1$，$0 < ex\_i, ey\_i <1{,}000$。

输出

在一行中，输出以一个空格分隔的两个数字：桥梁的长度和满足市长需求的高速公路（即桥梁和两条道路）的总长度。输出的绝对或相对误差不超过 $10^{-8}$。

示例输入 1

200 500 800 500
3
400 0
450 500
400 1000
3
600 0
550 500
600 1000```

### 示例输出 1

```plain
100 600```

* * *

### 示例输入 2

```plain
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

```plain
200 541.421356237```

* * *

### 示例输入 3

```plain
300 400 700 600
2
400 0
400 1000
2
600 0
600 1000```

### 示例输出 3

```plain
200 482.842712475```

* * *

### 示例输入 4

```plain
200 500 800 500
3
400 0
450 500
400 1000
5
600 0
550 500
600 100
650 500
600 1000```

### 示例输出 4

```plain
100 1200.326482915```

* * *