← 返回题目列表

AtCoder · icpc2015autumn_i

I. 最短的桥梁

中文机器翻译题面 查看原题

问题陈述

有一座城市,其形状为 $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