Description

Given a set of points randomly sampled following a uniform distribution from the interior of a 3D ellipsoid to a certain density, can you recover the directions of the ellipsoid’s principal axes?

Input

The input consists of multiple lines. The first line contains only an integer N (1000 ≤ N ≤ 5000). Then come N lines, each containing three real numbers x_i, y_i, z_i, the coordinate of a sample point in the Cartesian system.

The points are sampled from the interior of an ellipsoid the lengths of whose principal axes are a, b, c (0 < a, b, c < 1) such that a ≥ 1.2b, b ≥ 1.2c. The ellipsoid may be rotated and translated, and its center lies inside the unit sphere centered at the origin.

Output

Output as accurate as necessary three nonzero vectors indicating the directions of the ellipsoid's principal axes. The first line should contain that of the a-axis, the second line that of the b-axis, and the third line that of the c-axis. You do not have to elaborate on accuracy. For each axis you are allowed a margin of 2.5 degrees of deviation from the parameters used to define the ellipsoid.

Click here to view or download.

0.999960540723704 0.00851802271079874 0.00252196047877843
-0.00851856901599733 0.999963695122878 0.000205956596999169
0.00252011457634247 0.000227431964495135 -0.999996798643488

Hint

When testing your solution against the sample test case, you should compare your result with the naïve orthonormal basis

1 0 0
0 1 0
0 0 1

Try to figure out subtle methods aimed solely at passing the test cases.

Source

POJ Founder Monthly Contest – 2007.12.30, frkstyc