#1702. 「THUPC 2019」能量波 / energywave

「THUPC 2019」能量波 / energywave

题目描述

有两个超级英雄在宇宙中战斗。英雄 A 为了击败对手英雄 B,使出了他的绝招,发出了一记能量光波。

英雄 B 有一些体力值,如果英雄 A 的能量光波对英雄 B 的伤害足够大,英雄 B 就会被击倒。否则英雄 A 就会因为耗尽能量而被英雄 B 抓住破绽,从而反而被英雄 B 击倒。所以英雄 A 迫切想知道自己的能量光波到底能够对英雄 B 造成多少伤害。

为了简化问题,英雄 B 可以被描述为空间中的多个凸多面体拼成的物体。这些凸多面体可能有重合的部分,重合部分作为英雄 B 的身体只会被计算一次。

英雄 A 发出的能量光波也可以被描述为空间中的另外一个凸多面体,这个光波在空间中每秒均匀移动一个向量 v=(vx,vy,vz)\vec{v} = (v_x,v_y,v_z)。能量光波可以穿过任何物体,并且在穿越的过程中对对方造成伤害。

在时刻 tt,假设英雄 A 的能量光波和英雄 B 的身体的交的体积为 f(t)=Vf(t) = V,那么在这一瞬间,能量光波造成的瞬时伤害速率就恰好是 VV。而所有时刻的总计伤害就可以被表示为

0f(t)dt\int_{0}^{\infty} f(t) dt

英雄 A 想要知道自己的能量光波对英雄 B 的身体造成了多大的总计伤害。

输入格式

11 行一个正整数 mBm_B,表示英雄 B 的身体有多少个凸多面体组成。

接下来有 mBm_B 个输入块,每块表示英雄 B 的身体的一个组成部分。
每个输入块开头第一行为一个正整数 nn,表示这个凸多面体的顶点的个数,

接下来 nn 行每行一个三元组,其中第 ii(xi,yi,zi)(x_i,y_i,z_i) 表示第 ii 个点的坐标。
接下来一行一个正整数 nAn_A,表示英雄 A 的能量光波的对应凸多面体的顶点数,

接下来 nAn_A 行每行一个三元组,其中第 ii(xi,yi,zi)(x_i,y_i,z_i) 表示第 ii 个点的坐标。
再接下来一行一个三元组 (vx,vy,vz)(v_x,v_y,v_z),表示英雄 A 的能量光波的移动速度。

我们保证 1mB4,4n,nA81 \le m_B \le 4,4\le n,n_A\le 8 ,所有输入的点的坐标都是 [100,100][-100,100] 内的整数。并且所有速度向量的分量都是 [10,10][-10,10] 内的实数。所有凸多面体都是不退化的 (意思是这个凸多面体的体积非 00)。
输入中可能会出现四点共面或者三点共线的情况。
我们保证在第 00 秒能量光波和英雄 B 是不相交的。并且在第 10410^4 秒之后交集的体积一直是 00

输出格式

一行输出一个实数,表示总计伤害的值。

输出与标准答案的绝对误差或相对误差小于 10610^{-6} 就会被算作正确。

样例

1
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
8
2 0 0
2 0 1
2 1 0
2 1 1
3 0 0
3 0 1
3 1 0
3 1 1
-1 0 0
1.0000000000

数据范围与提示

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。