#P3804. pku 3862 Asteroids

    ID: 3006 传统题 1000ms 64MiB 尝试: 56 已通过: 9 难度: 8 上传者: 标签>CF2400提高+/省选-三维凸包组合枚举叉积点积混合积判断共面状态编码自定义排序规则四面体分解求多面体重心鸣谢Claris提供SPJ

pku 3862 Asteroids

题目描述

给定两个顶点数分别为 n,mn,m 的三维凸包,求任意让两个凸包不重合的放置下两个质心之间的最小距离。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行三个整数 x,y,zx,y,z 描述第一个凸包的一个顶点。

接下来一行一个整数 mm。

接下来 mm 行,每行三个整数 x,y,zx,y,z 描述第二个凸包的一个顶点。

顶点均按乱序给出。

输出格式

输出一行一个实数表示答案,你的答案不应该和标准答案相差超过 10−510^{-5}。

8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
5
0 0 5
1 0 6
-1 0 6
0 1 6
0 -1 6
0.75

数据规模与约定

对于 100%100\% 的数据,4≤n,m≤604\leq n,m\leq 60,−104≤x,y,z≤104-10^4\leq x,y,z\leq 10^4。