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-28 15:08:04 UTC 由爬虫自动更新

共提交 0

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

·

·

·

·

登陆或注册以提交代码