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: 3000MSMemory Limit: 131072K
Total Submissions: 116Accepted: 24Special Judge


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?


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 xi, yi, zi, 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 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.

Sample Input

Click here to view or download.

Sample Output

0.999960540723704 0.00851802271079874 0.00252196047877843
-0.00851856901599733 0.999963695122878 0.000205956596999169
0.00252011457634247 0.000227431964495135 -0.999996798643488


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.


[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