Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 126Accepted: 49


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.

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



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator