当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

4010:Shadow

题目描述
Somewhere in the universe, Orez is a planet which has highly developed civilization and advanced technology. But unfortunately, a supernova which is near to Orez blossomed and emitted an extraordinary radiation that may danger the civilization in Orez.

There is a great fleet of spaceship in the planet. The fleet has ONE battle-cruiser and several fighters. A fighter can make a sphere magnetic shield which the radiation can’t pass through. When the fleet is in the space, the battle-cruiser and the magnetic shields can make shadows on the ground if the radiation comes.

When the radiation hit the planet, people in Orez will be destroyed except they go into the shadow of the fleet. So we want to know the area of the safety shadow.

To simplify this problem, you can consider that: the ground is an infinity plane, the radiation is parallel light, a fighter is a point, and the battle-cruiser is a 3D convex hull.
输入解释
The input consists of multiply test cases.
For each case, the first line contains five integers: N, M, Dx, Dy and Dz. N is the number of fighters. M points in/on the battle-cruiser will be given later. The convex hull of these M points is the shape of the battle-cruiser. (Dx, Dy, Dz) is the direction vector of the radiation. Dz is negative.

Each of the next N lines contains four integers Xi, Yi, Zi and Pi , representing a fighter. (Xi, Yi, Zi) is the coordinate of the fighter (also the center of the sphere shield made by the fighter). Pi is the radius of the shield.

Each of the next M lines contains three integers Xi, Yi and Zi. (Xi, Yi Zi) is a point in/on the battle-cruiser.

All the Xi, Yi are in the range of [0, 100]; all the Zi are in the range of [20,100];
0< Pi <= 20; N+M<=500, and the ground is the plane Z=0.

Please note that several fighters may stay at the same position, and a fighter can stay inside or on the cruiser.

The input ends with 0 0 0 0 0.
输出解释
For each case, print the area of shadow in a line. The result should be rounded to 4 digits after the decimal point.
输入样例
2 4 1 1 -1
25 22 30 14
24 32 27 15 
32 40 21 
21 30 21 
20 21 22 
20 30 22
0 0 0 0 0
输出样例
1539.3185

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Fuzhou 2011

源链接: POJ-4010

最后修改于 2020-10-28T15:08:04+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536