Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Language: Shadow
Description 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. Input 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. Output For each case, print the area of shadow in a line. The result should be rounded to 4 digits after the decimal point. Sample Input 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 Sample Output 1539.3185 Source |
[Submit] [Go Back] [Status] [Discuss]
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator