P6923 [ICPC 2016 WF] Polygonal Puzzle

题目描述

有两个多边形，可以平移旋转（但不能对称、缩放等），求这两个多边形贴在一起但不重合的情况下贴贴部分的最大总长度。

输入格式

第一行一个数字 $n_1$，表示第一个多边形是 $n_1$ 边形。

接下来 $n_1$ 行，每行两个数字，表示第一个多边形每个端点的横、纵坐标。

接下来一个数字 $n_2$，表示第二个多边形是 $n_2$ 边形。

最后 $n_2$ 行，每行两个数字，表示第二个多边形每个端点的横、纵坐标。

输出格式

一行，最大的贴贴部分长度，绝对误差或相对误差任一小于 $10^{-3}$ 即可通过。

输入输出样例 #1

输入 #1

8
0 0
0 10
10 10
15 15
24 6
24 10
30 10
30 0
7
-5 0
-5 10
10 10
15 5
20 10
35 10
35 0

输出 #1

30.142135624

输入输出样例 #2

输入 #2

3
1 0
0 30
40 0
3
1 0
0 30
40 0

输出 #2

50

说明/提示

$3 \leq n_1, n_2 \leq 50$，横纵坐标均为整数且绝对值不超过 $100$。