问题描述 :
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.
输出:
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.
样例输入:
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
