#P4615. [Wf2016]Polygonal Puzzle

    ID: 3291 传统题 6000ms 512MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-枚举与搜索暴力枚举模拟与实现技巧坐标变换计算几何耳切法三角剖分Minkowski 和Andrew 算法投影多项式与生成函数分段多项式扫描线离线与分治扫描中维护贡献同时事件分阶段处理动态规划有限候选集缩减CF3000

[Wf2016]Polygonal Puzzle

题目描述

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

输入格式

第一行一个数字 n1n_1,表示第一个多边形是 n1n_1 边形。

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

接下来一个数字 n2n_2,表示第二个多边形是 n2n_2 边形。

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

输出格式

一行,最大的贴贴部分长度,绝对误差或相对误差任一小于 10−310^{-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≤n1,n2≤503 \leq n_1, n_2 \leq 50,横纵坐标均为整数且绝对值不超过 100100。