GALACDIV - Galactic Division

The scientists of UEA (Universal Environment Association) are currently researching the outer space, they found out that a plane in the space had some interesting properties on a set of planes based on its balance factor. The balance factor is equal to the absolute value of the differente between the sum of distances of the planets which are on one side of the plane and the sum of the distances of the planets which are on the other side, the distance of a planet to the plane is calculated as the distance from the center of the planet to the plane.

The scientists are marveled with the results they found when the balance factor of a plane is minimal, but as they are manually calculating the balance factor, when the set of planets become larger, they find it harder to calculate. So they hired you to build a program that given a set of N planets and a 3D vector (vx, vy, vz) returns the coefficients of the general equation of the plane that has minimal balance factor and is normal to the vector given.


The input contains several test cases. The first line of a test case contains an integer N (1 ≤ N ≤ 106), indicating the number of planets. The second line contains three integers which are the components vx, vy e vz of the vector (-103vx, vy, vz ≤ 103). Each of the following N lines contains three integers X, Y and Z (−104X, Y, Z ≤ 104), representing the position (X, Y, Z) of the center of a planet. There won't be a vector which components are vx = vy = vz = 0.


For each test case in the input your program must produce a single line containing four integer which are the coefficients a, b, c and d of the general plane equation (ax+by+cz=d). As there may be several planes that meet the specifications, print the coefficients which absolute values are the smallest possible and a, b and c have the same sign as vx, vy and vz, respectively.


1 2 3
0 0 0
0 1 0
0 0 0
2 2 2 Output: 1 2 3 0
0 1 0 1

hide comments
julkas: 2018-06-19 10:10:06

Good classic problem. Carefully read description.

Added by:Erick Monteiro
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)